codeforces 776C Molly's Chemicals(连续子序列和为k的次方的个数)

题意：给出一个有n个数的序列，还有一个k，问在这个序列中有多少个子序列使得sum[l, r] = k^0,1,2,3……

思路：sum[l, r] = k ^ t, 前缀和sum[r] = sum[l-1] + k^t。即如果后面有一段序列使得sum[l,r] = k^t，那么它可以转化为前缀和相减使得这一段大小为k^t，即sum[i] = sum[j] + k^t (1 <= j < i)。

那么对于处理好的每一个前缀和，直接往后面加上k^t（0<=t<=x,k^x是不超过题目范围的数）。然后在后面遍历的时候直接加上对应那个数的权值。

因为数据很大，所以只能用map来装权值。

代码实现：

 #include<bits/stdc++.h>

 #define ll long long

 using namespace std;

 ll f[];

 ll k_t[];

 int main()

 {

     int n,k,i,j,cnt;

     while(cin>>n>>k)

     {

         map<ll,int>mp;

         memset(f,,sizeof(f));

         memset(k_t,,sizeof(k_t));

         for(i=;i<=n;i++)

         {

             cin>>f[i];

             f[i]+=f[i-];

         }

         k_t[]=;cnt=;

         if(k==-)k_t[]=-,cnt++;

         else if(k!=)

         {

             ll temp=k;

             while(temp<1e15)

             {

                 k_t[cnt++]=temp;

                 temp*=k;

             }

         }

         ll ans=;

         for(i=;i<cnt;i++)mp[k_t[i]]=;

         for(i=;i<=n;i++)

         {

             if(mp[f[i]])ans+=mp[f[i]];

             for(j=;j<cnt;j++)

             mp[f[i]+k_t[j]]++;

         }

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

codeforces 776C Molly's Chemicals(连续子序列和为k的次方的个数)

最新文章

热门文章