题解：CF1626F A Random Code Problem
xplor
·
·
题解
思路
题目欲求 E \times n^k = \frac {\sum ans}{n^k} \times n^k 即为 \sum ans。
考虑计算每个位置的贡献。
设 f_{i,j} 为前 i 次操作中 j 的出现个数。
则有：
$dp_{i + 1,j} = dp_{i + 1, j - j \bmod i} + dp_{i, j}$。
由于 $x|y - y \bmod x$， 所以 $a$ 的每个数最后一定是 $[1,2,...,k - 1]$ 的倍数，所以减去这部分值是可行的（不会影响 $\frac {j}{[1,2,...,k - 1]} \times [1,2,...,k-1]$ 的值）。
用动态规划维护余数，每个数皆小于 $720720$，可以通过。