首页 > 代码库 > 20140710 sequence

20140710 sequence

2024-07-11 16:35:49   220人阅读

考试的时候想了好久都没想出正解 >_<

后来一听正解觉得很简单。。。只怪当时没想到

对前缀和取余

对于两个余数相等的前缀和 sum[i] 和 sum[j]

子串 i~j 即为符合条件子串

注意要处理有负数的情况 要保证每个前缀和取余后都要为正

最后对于余0的再加一遍即可

 1 #include <cstring> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 #define N 500500 6 typedef long long LL; 7  8 int n,k; 9 int num[N];10 int sum[N];11 LL ans;12 13 int main() {14     scanf("%d%d",&n,&k);15     sum[0]=0;16     memset(num,0,sizeof(num));17     for (int i=1;i<=n;i++) {18         scanf("%d",&sum[i]);19         sum[i]=sum[i]%k;20         if (sum[i]<0) sum[i]+=k;21         sum[i]=(sum[i]+sum[i-1])%k;22         ans+=num[sum[i]];23         num[sum[i]]++;24     }25     ans+=num[0];26     printf("%lld",ans);27 }
View Code

 


联系
我们