简要题意.

给定 $N,M,K$ 和序列 $A_1, A_2, \dots, A_N$，有一个变量 $X$ 初始为 $0$，接下来每一步将会以正比于 $A_v$ 的概率使 $X \gets (X+v) \bmod M$，问得到 $K$ 的期望步数。

$N\le 500$，$M \le 10^{18}$，$A_i \le 100$。

DP，设 $f_i$ 表示从 $0$ 到 $i$ 的期望步数，反过来变成从 $i$ 到 $0$ 的期望步数，有 $$ \left\{ \begin{aligned} f_0 &= 0 \\ f_i &= 1+\sum_{j=1}^N p_j f_{(i-j)\bmod M} \quad (0 < x < M) \end{aligned} \right. $$

一个关键的性质是，有 $$ f_i = 1+\sum_{j=1}^N p_j f_{i-j} \quad (i \ge N) $$

这是一个常系数线性非齐次递推。容易化为齐次递推：

$$ f_i = f_{i-1} + \sum_{j=1}^{N+1} (p_j-p_{j-1}) f_{i-j} \quad (i > N) $$

从而我们可以用 $f_0, f_1, \dots, f_N$ 表出任意 $f_i$；进一步，只需 $1, f_0, f_1, \dots, f_{N-1}$。

那么我们求出 $f_{M-N,\dots,M-1}$ 的表示（可以先用快速幂算出 $x^{N-M} \bmod P(x)$，然后每次乘 $x$ 后取模，其中 $P(x)$ 是特征多项式），即可解出 $f_0, f_1, \dots, f_{N-1}$。然后执行线性递推远处求值即可得到 $f_K$。时间复杂度 $O(N^3 + N^2 \log M)$。