题解：CF1626F A Random Code Problem

题目欲求 $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} + (n - 1) \times dp_{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$，可以通过。