萌新刚学概率，再求问

学术版

ningago @ 2022-06-20 18:50:39

RT。

萌新求助求期望：

① 如果有绕圈（例如 f_{x,y}\to f_{x+1,y} \to f_{x,y}）或者无限循环（例如 f_{x,y}\to f_{x+1,y} \to f_{x+2,y} \to \cdots），这种情况对答案的贡献是什么？如何计算？

② 这二者大部分都是不能直接通过题意来记忆化搜索（dp）实现的，那么通常如何设计状态使得可以期望 dp 求解

③ 上面的情况如果不能直接 dp 转移是不是只能在高斯消元或者其它消元方法求解并利用数学优化复杂度？

by luogubot @ 2022-06-20 18:53:21

首先有关于状态数 n 的 O(n^3) 高斯消元做法，另外注意到带状矩阵高斯消元是 O(nd^2) 的，你可以理解其为手动消元，比如 BJOI 光线是 d=2 还是啥的手动消元。

by ningago @ 2022-06-20 18:55:28

@luogubot 但蒟蒻的意思是还有没有别的方法

by luogubot @ 2022-06-20 18:57:21

在求实数并且精度要求没那么高的时候可以迭代

by Prean @ 2022-06-20 19:04:12

如果不取模的话可以n^2暴力迭代几轮（

by ningago @ 2022-06-20 19:07:37

@Prean wtcl，能给个迭代的代码吗伪的也行

by lingfunny @ 2022-06-20 19:31:13

感觉算不了，除非贡献是可以看出来的，比如这题 CF908D. New Year and Arbitrary Arrangement

by lingfunny @ 2022-06-20 19:44:21

或者说你可以看它的生成函数（

|