codeforces怎么提交，codeforces 776C Molly's Chemicals(連續子序列和為k的次方的個數)

2023-10-21 阅读 22 评论 0

摘要：題目鏈接題意：給出一個有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，那

題目鏈接

題意：給出一個有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是不超過題目范圍的數）。然后在后面遍歷的時候直接加上對應那個數的權值。

codeforces怎么提交？因為數據很大，所以只能用map來裝權值。

代碼實現：

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 ll f[101005];
 5 ll k_t[1000];
 6 int main()
 7 {
 8     int n,k,i,j,cnt;
 9     while(cin>>n>>k)
10     {
11         map<ll,int>mp;
12         memset(f,0,sizeof(f));
13         memset(k_t,0,sizeof(k_t));
14         for(i=1;i<=n;i++)
15         {
16             cin>>f[i];
17             f[i]+=f[i-1];
18         }
19         k_t[1]=1;cnt=2;
20         if(k==-1)k_t[2]=-1,cnt++;
21         else if(k!=1)
22         {
23             ll temp=k;
24             while(temp<1e15)
25             {
26                 k_t[cnt++]=temp;
27                 temp*=k;
28             }
29         }
30         ll ans=0;
31         for(i=1;i<cnt;i++)mp[k_t[i]]=1;
32         for(i=1;i<=n;i++)
33         {
34             if(mp[f[i]])ans+=mp[f[i]];
35             for(j=1;j<cnt;j++)
36             mp[f[i]+k_t[j]]++;
37         }
38         cout<<ans<<endl;
39     }
40     return 0;
41 }