首页 > 代码库 > 前缀和（vijos1090连续数之和）

前缀和（vijos1090连续数之和）

2024-09-29 11:46:02   220人阅读

描述

有n个正整数排成一行。你的目的是要从中取出一个或连续的若干个数，使它们的和能够被k整除。

例如，有6个正整数，它们依次为1、2、6、3、7、4。若k=3，则你可以取出1、2、6，或者2、6、3、7，也可以仅仅取出一个6或者3使你所取的数之和能被3整除。当然，满足要求的取法不止以上这4种。事实上，一共有7种取法满足要求。

给定n和k，以及这n个数。你的任务就是确定，从这n个数中取出其中一个数或者若干连续的数使它们的和能被k整除有多少方法。

由于取法可能很多，因此你只需要输出它mod 1234567的值即可。

输入格式

第一行有两个正整数，分别代表n和k。输入数据保证有n<=500 000，k<=100 000。

以下n行每行一个正整数。这些正整数保证都不大于10 000。

输出格式

一个正整数。它应该是你的答案mod 1234567的结果。

样例输入1

6 3126374

样例输出1

7
看到本题之后第一反应肯定是前缀和，但是用普通的前缀和并不可以成功Ac，而是tle。
于是我们就可以从前缀和的公式出发sum[j]-sum[i-1]%k==0也就是sum[j]和sum[i-1]同余。
我们就可以用一个book数组记录余数，然后用组合公式求出解即可。
Tips：单独的一个book[0]也是可以算一种解的，所以答案要在最后加上book[0];
这是我的代码~
#include<bits/stdc++.h>#define mod 1234567using namespace std;int sum;int book[2000000];int n,m,k;int ans=0;int main(){	ios::sync_with_stdio(false);	cin>>n>>k;	for(int i=1;i<=n;i++)	{		cin>>m;		sum+=m;		sum%=k;		book[sum]++;	}	ans=book[0];	for(int i=0;i<k;i++)		ans+=book[i]*(book[i]-1)>>1;	cout<<(ans)%mod<<endl;	return 0;}

　　如果大家看不懂的话，可以看一下下面以为拷贝vijos大神的解析：Orz 340508965

先说说怎么做吧SUM[i]是代表前i个数的和 当(SUM[i]-SUM[j]) MOD k=0 这时[j+1,i]就是满足的一个区间 一个方案了 而我们求的是(SUM[i]-SUM[j]) MOD k=0 这样的方案总个数 我们又可以推出 上式等价于SUM[i] MOD k=SUM[j] MOD k 所以我们就是求SUM[i] MOD k=SUM[j] MOD k 的方案个数了假设 sum[i],sum[j],..sum[k]（共bn个） 都是 MOD k 余数为k-1的sum 那么从上面bn个sum中任意选取两个就能得出(SUM[i]-SUM[j]) MOD k=0 那么在bn个sum中怎么配对呢（下面的sum[bn]表示上述bn个sum中的第n个sum） 很简单 先是sum[b1]与sum[b2] sum[b3] ...sumbn 　　 然后sum[b2]与sum[b3] sum[b4] ...sumbn 　　 然后sum[b3]与sum[b4] sum[b5] ...sumbn 　　 ............ 　　 最后sum[bn-1]与sum[bn]　　　　　　　　 ( 1 个)　　 方案总数=n-1+n-2+n-3+...+1=bn*(bn-1) div 2 （好像这是初中的知识吧？ 可是当时我看楼下的楼下的楼下....的题解 我一时竟然还不明白为什么）所以 当sum mod k的余数为k-1时有bn*(bn-1) div 2个方案总数了 就这样依次得出余数为k-1 k-2 k-3 ...0的时候方案总数 再相加一下得出答案所以在读入一个数的时候就计算sum然后计算sum mod k 的余数 而b[j]表示余数为j的sum个数 此时根据上面新得出的更新相应的b[j]这样在读入完毕之后就可以根据b[j]直接计算总方案数了特别值得注意的是！！！！ 计算余数为0的方案总数时候还要加上b[0]　　也就是b[0]*(b[0]-1) div 2+b[0] 为什么？？ 因为余数为0的时候单独一个sum[i]就能成为一个方案了还有比如div 2可以用shr 1 这样可以加快速度呼呼(～ o ～)~zZ　　说得好累啊 我自己都快被讲糊涂了 呵呵 希望有不懂这道题目的人能看懂.... 这样就不算白忙了

 

 

前缀和（vijos1090连续数之和）


联系
我们