题目链接:JZOJ 2644。
题目
题目描述
给你一个长度为 $n$ 的正整数序列,如果一个连续的子序列,子序列的和能够被 $k$ 整除,那么就视此子序列合法,求原序列包括多少个合法的连续子序列?
输入格式
第一行,$\text{T}$,表示数据组数。
对于每组数据:
第一行,$2$ 个数,$K,N$。
第二行,$N$ 个数,表示这个序列。
输出格式
共 $\text{T}$ 行,每行一个数表示答案。
样例输入输出
1
- Input:
2
7 3
1 2 3
4 8
2 1 2 1 1 2 1 2
- Output:
0
6
数据范围
$$1\leq \text{T}\leq 20,1\leq n\leq 5\times 10^4,1\leq k\leq 10^6$$
时空限制
$$\text{JZOJ}:1\text{s}/256\text{MiB}$$
题解
解法 A(直接模拟)
思路
直接按照题意模拟,枚举左右端点,再求和,最后判断能否被 $k$ 整除。
代码
代码在这里就不给出了,算法的渐进时间复杂度为 $\Theta(n^3)$。
解法 B(优化模拟)
思路
用前缀和优化求和过程,使得求和的时间复杂度降为了 $\Theta(1)$。
代码
代码实现比较简单,就不给出了,算法的渐进时间复杂度为 $\Theta(n^2)$。
解法 C(正解)
思路
记原数组为 $a _ i$。
先对数组 $a _ i$ 求前缀和,设 $\text{sum} _ i=\sum^{i} _ {j=1}a _ j$。
然后,我们分析问题,得出合法序列的条件,即 $\sum^r _ {i=l}a _ i\equiv 0\pmod k$。
转化为前缀和,得出:$\text{sum} _ r-sum _ {l-1}\equiv 0\pmod k$。
那么我们根据排列组合,可以得出结论。
设满足条件 $\text{sum} _ i\equiv x\pmod k$ 的 $\text{sum} _ i$ 的数量为 $\text{Times} _ i$,那答案就是:
$$\sum^{k-1} _ {i=0}\left\lfloor\left|\frac{\text{Times} _ i\times(\text{Times} _ i-1)}{2}\right|\right\rfloor$$
最终的时间复杂度度为 $\Theta(n+k)$ (还使用桶可以优化到 $\Theta(n)$)。
代码
代码如下,比较简单。
#include<cstdio>
#include<cstring>
typedef long long ll;
const int MAXN=50000+5;
const int MAXK=1000000+5;
int T,n;
ll k;
ll a[MAXN],sum[MAXN];
ll Times[MAXK];
int main(void){
register int i;
register ll ans;
scanf("%d",&T);
while(T--){
ans=0;
memset(Times,0,sizeof(Times));//初始化
scanf("%lld%d",&k,&n);
for(i=1;i<=n;++i){
scanf("%lld",&a[i]);
sum[i]=(sum[i-1]+a[i])%k;
++Times[sum[i]];
}
++Times[0];//统计sum[0]
for(i=0;i<k;++i)
if(Times[i]>=2)
ans+=(Times[i]*(Times[i]-1))>>1;
printf("%lld\n",ans);//输出答案
}
return 0;
}
近期评论