题目
题解
思维。
暴力的话是会超时的,但也可以骗点分。
(采用差分数组暴力)
讲一下AC思路。
统计出来每个前缀和取模
k
k
k后结果的个数,比如
c
n
t
[
0
]
cnt[0]
cnt[0] 表示前缀和取模
k
k
k 等于
0
0
0 的前缀个数;
c
n
t
[
1
]
cnt[1]
cnt[1] 表示前缀和取模
k
k
k 等于
1
1
1 的前缀个数;……
假设前缀和取模
k
k
k等于
1
1
1的全部前缀如下:
总共三个前缀,我们考虑任选其中的两个前缀,长前缀比短前缀多出的部分的数是否可以保证求和取模
k
k
k等于
0
0
0?
假设短前缀和为
S
u
m
s
h
o
r
t
Sum_{short}
Sumshort,长前缀和为
S
u
m
l
o
n
g
Sum_{long}
Sumlong,
S
u
m
l
o
n
g
−
S
u
m
s
h
o
r
t
Sum_{long}-Sum_{short}
Sumlong−Sumshort 为长前缀比短前缀多出的部分的数之和。
(
S
u
m
l
o
n
g
−
S
u
m
s
h
o
r
t
)
%
k
=
S
u
m
l
o
n
g
%
k
−
S
u
m
s
h
o
r
t
%
k
=
1
−
1
=
0
(Sum_{long}-Sum_{short})\%k=Sum_{long}\%k-Sum_{short}\%k=1-1=0
(Sumlong−Sumshort)%k=Sumlong%k−Sumshort%k=1−1=0
所以长前缀比短前缀多出的部分的数就是满足条件的一组数。如此一来,我们可以只需要在这三个前缀中选两个构成一组满足条件的数,即
C
3
2
C_3^2
C32 为前缀和取模为
1
1
1 的前缀能构成取模
k
k
k 等于
0
0
0 的序列的方案数。
特殊地,对于前缀和取模
k
k
k为
0
0
0的前缀能组合出满足条件的序列的个数还需要加上它们自己,也就是我们可以把每一个满足前缀和取模
k
k
k为
0
0
0的前缀单拎出来,它们还是满足和取模为
0
0
0的要求,因此,还要将这些方案加上。
在代码实现上,我们只需要将
c
n
t
[
0
]
cnt[0]
cnt[0] 初始化为
1
1
1 即可,因为
C
n
+
1
2
=
C
n
2
+
n
C_{n+1}^{2} = C_{n}^{2} + n
Cn+12=Cn2+n
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
LL n, k, a, s, cnt[N], ans;
int main()
{
cin >> n >> k;
cnt[0] = 1;
for (int i = 1;i <= n;i ++) {
cin >> a;
s += a;
cnt[s % k] ++;
}
for (int i = 0;i < k;i ++)
ans += cnt[i] * (cnt[i] - 1) / 2;
cout << ans << endl;
return 0;
}