模拟3神秘消失，人性的扭曲，道德的沦丧

随

这次的提示居然是有用的qaq
首先可以搞出一个概率的转移方程，因为 \(m\) 很大，所以可以用矩阵优化成 \(\log m\)
这样的复杂度是 \(mod^3\log m\) 的，据说可以有 80pts，然而这个 zz 人傻常数大，实际只有 20pts
这里有一个叫循环矩阵的东西，即每一行都是上一行向右循环平移得来的
这种矩阵的性质就是，知道首行，就能推出所有，也就意味着可以做到 \(mod^2\) 单次的矩阵乘法
现在我们的复杂度瓶颈就在这里，所以考虑如何把普通的转移矩阵转化成循环矩阵的形式
在之前的方程中，有类似于 \(x\rightarrow x*a_i \% mod\) 的转移，对于每一个 \(a_i\)，这样算出的目标状态和起始状态差不一定，所以整个矩阵并不循环
那么这时用原根在模 \(\text{mod}\) 意义下化乘法为加法，就会发现在算矩阵系数时，行列编号差值一定了，也就意味着这样构造出来的矩阵循环
循环矩阵在加乘运算下保持循环性质，因此可以只记录一行，然后找规律做乘法
对于转移矩阵，把原根次数与原数互相映射后开桶记录，第 i 项即为 \(\frac{cnt_i}{n}\)
剩下的就是快速幂，然后按期望定义来计算答案即可

单

对于 \(t=0\) 的情况,可以发现能用换根 dp 统计，复杂度是 \(O(n)\) 的
而对于 \(t=1\) 的情况，仿照链部分分的方式，考虑每一对父子之间答案变动量
那么有 \(x\rightarrow y,b_x-b_y=sum_y-(Sum-sum_y)\)，其中 \(sum\) 记录子树 \(\sum a_i\)，\(Sum\) 为所有 \(a_i\) 之和
这样的关系式有 \(n-1\) 个，将他们相加可以得到：\(2\sum sum_y-(n-1)Sum=\sum(b_x-b_y)\)
这里一个关键的转化是 \(\sum sum_y=b_{root}\)，因为对于每个 \(a_i\) 都在左边贡献了 \(dep_i\) 次，和 \(b_{root}\) 的定义相同
这样就可以求出 \(Sum\)，进而求出每一个 \(sum_i\)，然后类似于树上差分即可求出每个 \(a_i\) 了

题

\(t=0\)：枚举上下、左右方向的步数 \(2x,2y\)，答案为 \(\sum\limits_x\sum\limits_y\pmatrix{n\\2x}\pmatrix{2x\\x}\pmatrix{2y\\y}\)，没啥刁钻的地方就可以直接算
\(t=1\)：相当于长度为 \(n\) 的进出栈/括号序列数，即为卡特兰数 \(Cat_{n/2}\)
\(t=2\)：直接二维状态来 dp 统计即可
\(t=3\)：相当于在两个方向上的进出栈/括号序列数，那么需要枚举两个方向步数 \(2x,2y\)，答案为 \(\sum\limits_{x+y=n/2}\pmatrix{n\\2x}Cat_xCat_y\)
考试时看没时间就直接暴力计算了，还是需要用时间思考一下……

大佬

各位大佬先改吧 我XIN队还没学明白 （-q-）