題目鏈接
題意:給出一個有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 }
?