题解 CF1305C 【Kuroni and Impossible Calculation】
xht
2020-03-06 13:16:07
这个绝对值看起来不太好搞，那么我们排序一下，就一定是后面减前面了。
依次考虑每个数与前面的数对答案的贡献，但我们显然不能 $\mathcal O(n^2)$ 枚举。
注意到这个模数非常小，因此我们对前面的数开一个桶，记录每个余数的个数。
那么我们只需要 $\mathcal O(nm)$ 就可以求出每个可能的差的数量，最后快速幂一下就能求出答案了。
什么，你问 $\mathcal O(nm)$ 不是 $2 \times 10^8$ 吗，怎么能过？
你要相信 CF 神机一秒跑十亿不成问题。
```cpp
const int N = 2e5 + 7, M = 1e3 + 7;
int n, a[N], c[M];
ll f[M];
modint ans = 1;
int main() {
rd(n), rd(P), rda(a, n);
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
a[i] %= P;
for (int j = 0; j < P; j++)
f[(a[i]-j+P)%P] += c[j];
c[a[i]]++;
}
for (int i = 0; i < P; i++) ans *= (modint)i ^ f[i];
print(ans);
return 0;
}
```