Problem
小b喜欢和为K的倍数的序列。
现在有一个长度为n的序列A,请问A有多少个非空连续子序列是小b喜欢的。
Solution
求一个前缀和,mod k,如果数组i和j(i<=j)位置相等,则从i+1到j位置的序列和为k的倍数,任选两个即可,k不大,用数组记录,注意0的时候包含本身。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| #include<iostream> #include<stdio.h> #include<algorithm> using namespace std; #define io_opt std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) int n,k,a[30020],ans; int sum[30020]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } scanf("%d",&k); for(int i=1;i<=n;i++){ a[i]+=a[i-1]; a[i]=(a[i]+k*10000)%k; sum[a[i]]++; } ans+=sum[0]; for(int i=0;i<k;i++){ if(sum[i]) ans+=(sum[i]*(sum[i]-1))/2; } printf("%d\n",ans); return 0; }
|