AtCoder ARC114 总结
A
50 内只有 15 个质数。\(2^{15}\) 枚举所有情况然后 \(O(n)\) check 即可。
B
若 \(i\to f(i)\) 连边，原题意相当于选出若干个环。答案即 \(2^{\text {环数}}-1\)。
C
考虑一开始每个数都有 \(1\) 的贡献，总贡献即 \(m^n\times n\)，然后把多余贡献剪掉。对于 \(a_i=a_j\)，若所有 \(i<k<j\) 都有 \(a_k>a_j\) 则贡献可以减一。我们要求
\[\sum _{i=1}^n\sum_{j=i+1}^n\sum _{k=1}^m(m-k)^{j-i-1}m^{n-j+i-1}
\]
枚举 \(j-i\)，可以做到 \(O(n^2)\) 或 \(O(n^2\log n)\)。