传送门:https://ac.nowcoder.com/acm/contest/7079/D

题意:在一个有n个点的环上，每个点上有一些人。每个人每一步独立的以 p1 的概率向左走,p2的概率向右走。p3的概率留在原地。问k轮之后每个点的期望人数分布情况.

问题1:n , k <= 100.

不难想出状态:f(i,j)代表第j轮之后站在第i个点上的期望人数.

问题2:n <= 100 , k <= 1e18

k十分大,自然想到加速dp过程的方法:矩阵快速幂

由于是二维的转移方程,我们需要构造一个 n * n 的矩阵来进行暴力的转移.

将状态的含义改变为:f(i,j)代表一个人从0开始,第j轮之后站在第i个点上的概率.

将结果矩阵算出来.最后乘上每个点的人即可.

问题3:n <= 500 , k <= 1e18

发现转移矩阵是一个循环矩阵.所以理论上我们只需要一行即可实现矩阵乘法.那么复杂度可以降至

循环矩阵 * 循环矩阵 = 循环矩阵

转移的时候注意:令res为当前结果矩阵,tran为转移矩阵.

存在规律:

而且由于循环,每个点的移动情况本质上是一样的.所以可以通过平移的方式统一计算0点开始的结果.

AC代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44871810

问题4:n <= 5e4, k <= 1e18

上式是卷积形式,可以上FFT.太难了,我不会