Cerința

Se dă un şir format din n numere naturale nenule. Să se afle numărul secvenţelor din şir care au produsul elementelor egal cu 2k, unde k este un număr natural dat.

Date de intrare

Fișierul de intrare memory006.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule, separate prin spații.

Date de ieșire

Fișierul de ieșire memory006.out va conține pe prima linie numărul S, reprezentând numărul secvenţelor din şir care au produsul elementelor egal cu 2k.

Restricții și precizări

• 1 ≤ n ≤ 500.000
• 1 ≤ k ≤ 10.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mari decât 1 şi mai mici decât 1018

Exemplu

memory006.in

5 3
7 4 2 4 5

memory006.out

2

Explicație

Avem n=5,k=3. În şirul dat există două secvenţe care au produsul elementelor egal cu 23, şi anume 4,2 şi 2,4.

#include <bits/stdc++.h>
using namespace std;

ifstream fin("memory006.in");
ofstream fout("memory006.out");

long long n,k,i,suma,nr,x,st,dr,p[60];
long mij;
char a[10001],t,j;

char exp(long s,long d)
{
    if(s>d) return 0;
    mij=(s+d)/2;
    if(x==p[mij])
        return mij;
    if(x<p[mij])
        return exp(s,mij-1);
    else
        return exp(mij+1,d);
}

int main()
{
    fin >> n >> k;
    p[1]=2;
    for(i=2;i<=57;++i)
        p[i]=p[i-1]*2;
    nr=0;
    suma=0;
    st=0;
    dr=-1 ;
    for(i=0;i<n;++i)
    {
        fin>>x;
        t=exp(1,57);
        if(t==0)
        {
           suma=0;
           st=0;
           dr=-1;
        }
        else
        {
           dr=(dr+1)%10001;
           a[dr]=t ;
           suma=suma+t;
           if(suma>=k)
           {
              if(suma==k)
                ++nr;
              else
              {
                while(suma>k)
              {
                  suma=suma-a[st];
                  st=(st+1)%10001;
              }
              if(suma==k)
                ++nr;
              }
           }
        }
    }
    fout << nr;
    return 0;
}