「题解」数列

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