[toc]

题目链接：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;
}