算法
(前缀和、同余) $O(N\log N)$
暴力做法的计算量为 $O(N^3)$,通过前缀和技巧可以降到 $O(N^2)$,但依然过不了。。。⊙︿⊙
记 $S_i = \sum\limits_{k = 1}^i A_k$
若 $(A_l + A_{l + 1} + \cdots + A_r) \equiv 0 \pmod M$,则有 $S_r - S_{l - 1} \equiv 0 \pmod M$,于是有 $S_r \equiv S_{l - 1} \pmod M$。所以,我们只需把每个 $S_i$ 对 $M$ 取模,然后开一个 std::map
用来记录 $S_i$ 出现的次数,接着扫描每个 $S_i$,把在位置 $i$ 之前出现的 $S_i$ 的次数加入答案,同时更新 $S_i$ 的次数。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::map;
using std::vector;
using ll = long long;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<int> s(n + 1);
rep(i, n) s[i + 1] = (s[i] + a[i]) % m;
map<int, int> mp;
ll ans = 0;
rep(i, n + 1) {
ans += mp[s[i]];
mp[s[i]]++;
}
cout << ans << '\n';
return 0;
}
^_^