（没打完的题解）
一定要看题看题看题看题看题看题
组合数求卡特兰阶乘逆元开到2n
脑残的审题错误：
1.T1 $1 leq a_i < mod$ 没看到qwq，然后觉得对于测试点一，输出1当且仅当ai都为奇数，显然0的可能性比较大，然后我就puts("0");了eee
2.T3 慌到数据范围看不清，认为对于所有opt的梯度都是100 1000 100000 然后想了半天opt==2且n<=100000时怎么搞，最后为了保分码了个$O(n^2)$暴力（我认为的）。出分后RE 90，我很蒙蔽，最后发现是tmd数组开小了 fffffffffffffuck!!!!!!
T2 $O(n)$做法 一闪而过，然后。。。就真pass了。。。
A. 随 (rand)
考察概率和期望的求解,矩阵乘法,原根的性质,循环矩阵的性质,倍增优化DP. 首先需要注意到虽然n可以达到10^5,但相同数字可以合并考虑,只需要考虑mod个不同的数字及选择它们的概率. 第1个测试点:mod=2,则n个数字都是1,直接输出1即可. 第2个测试点:每次乘上去的数字只有一种选择,快速幂即可. 第3,4,5个测试点:定义f[i][j]表示i次操作后x的数值为j的概率.直接转移,复杂度O(m*mod^2) 第6,7,8个测试点:第3,4,5个测试点中的DP转移可以转化为矩阵乘法形式,利用矩阵快速幂进行优化,复杂度O(mod^3*logm) 第9,10个测试点(标算):利用原根进行转化,则乘法转化为加法,f[i][j]表示i次操作后x取模后等于原根的j次方的概率.指数需要对(mod-1)取模.这样转化一下我们发现转移还是矩阵的形式,而且是循环矩阵的形式.循环矩阵快速幂,复杂度O(mod^2*logm) 另一种标算:定义f[i][j]表示i次操作后变成原根的j次方的概率.求出g[i][j]表示2^i次操作后变成原根的j次方的概率.倍增的思想求出f[m][]这个数组.也是O(mod^2*logm) 更加优越的算法:本质上我们要做的是循环卷积,可以使用fft.但本题的模数使得fft较为不方便..
题目求期望：$ E=Px $
转化为求概率P
$ P = frac {该结果的方案数} {总方案数} $
$ E=sum P_ix_i \ E=sum frac {该结果的方案数} {总方案数} imes x_i $
转化为求方案数
50pts：
预处理num[i]表示值为i的数字数量，知$1 leq num[i] < p$
然后暴力dp转移即可，复杂度$Theta (m p^2))$
柿子：$dp[i+1][j imes k \% p] = sumlimits_{j=0}^{p-1} sumlimits_{k=1}^{p-1} dp[i][j] imes num[k]$
加上前两个测试点共50分
100pts:
一辈子学不会矩乘qwq，只能靠倍增维持生活这样子
m很大，要么与其无关，要么带log
然后就想到了矩乘快速幂，然后在极其低效颓废的晚上肝矩阵 原根，还是没填完坑
然后今天早上换了个log，还是快速幂的思想，只不过我们倍增一个f[][]数组，也不用考虑什么goushi原根，直接倍增转移。
倍增f[i][j]数组，表示 $ 2^i $次转移到值为j的方案数
$ s & 2^i==1 \ dp[s][j imes k \% p] = sumlimits_{j=0}^{p-1} sumlimits_{k=1}^{p-1} dp[s'][j] imes f[2^i][k] $
B. 单(single)
标签:dfs，树形DP，高斯消元 分析:本题是一道二合一的问题,两个子任务相互对称. 算法1： t=0的数据最直接的想法是从每个点出发做一遍dfs,时间复杂度O(n^2),可以通过第1个测试点,期望得分10分 算法2： t=1的数据最直接的想法是枚举所有可能的a[]数组判断是否可行.第2个测试点n<=5,1<=a[i]<=20.注意20^5=3200000,直接暴力搜索a[i]的取值是可以承受的，可以通过第2个测试点,期望得分10分，结合算法1,期望得分20分. 算法3： t=1的数据中,b数组的表达式写出来之后,每个b[i]对应一个关于a[i]和树上两点距离的方程,例如b[1]=dis(1,1)*a[1]+dis(1,2)*a[2]+dis(1,3)*a[3]+...+dis(1,n)*a[n],于是可以列出n个方程用高斯消元求解,可以通过第2,3,4个测试点,期望得分30分,结合算法1,期望得分40分. 算法4： 对于测试点5,树退化为1条链。这个测试点的作用主要在于启发选手想到正解的思路。 t=0时，我们分别考虑编号小于i和大于i的点对b[i]的贡献.那么离得越远的点对答案的贡献越大.分别考虑每条边对答案的贡献,那么左侧的某条边对答案的贡献就是这条边左侧全部a[i]之和.实际上，我们对a[i]分别求取两次前缀和，两次后缀和即可完成对b[i]的计算. 记suf(i)为a[i]+a[i+1]+....+a[n-1]+a[n],pre(i)为a[1]+a[2]+...+a[i-1]+a[i],则b[i]=pre(1)+pre(2)+...+pre(i-1)+suf(i+1)+suf(i+2)+...+suf(n-1)+suf(n) 考虑t=1的情况. 我们知道suf(2)+suf(3)+...+suf(n)的值（即b[1]),知道pre(1) + suf(3) + suf(4) +...+suf(n)的值(即b[2]),知道pre(1)+pre(2)+suf(4)+...+suf(n)的值（即b[3]），注意到这些式子有很多项是一样的,考虑作差.可以得到下面的式子: b[2]-b[1]=pre(1)-suf(2),b[3]-b[2]=pre(2)-suf(3).....b[i+1]-b[i]=pre(i)-suf(i+1) 这些式子是有实际意义的,考虑从b[1]变到b[2]时答案的变化量,变化的就是1和2之间连边的贡献. 同时,记SUM=a[1]+a[2]+...+a[n-1]+a[n]，显然pre(i)+suf(i+1)=SUM,因此pre(i)=SUM-suf(i+1),将上面式子中所有pre换成suf，我们就知道了 SUM-2*suf(2) ,SUM-2*suf(3)...SUM-2*suf(n)的取值。 注意我们将n个式子作差之后得到了n-1个等式，实际上是丢弃了一些信息，只保留了b[i]之间的相对大小而忽略了b[i]自身的数值大小.于是考虑b[1]=suf(2)+suf(3)+suf(4)+... +suf(n),我们发现suf(2)到suf(n)都恰好出现了一次,而之前得到了n-1个形如SUM-2*suf(i)的式子，将这n-1个式子相加,suf(2),suf(3)...suf(n)前面的系数都是2,SUM的系数为(n-1),那么把这个式子加上2*b[1]，就得到了(n-1)*SUM,将求得的SUM代入之前的n-1个式子可以得到suf(2),suf(3),suf(4)......suf(n),差分一下即可得到a数组. 时间复杂度O(n),可以通过第5个测试点.推出这个做法,树上的做法也就不难想了. 算法5(满分算法): 考虑树上的问题. t=0的时候,我们可以先暴力计算出b[1],然后从b[1]出发开始dfs，由某个点的父亲的b[i]推出这个点的b[i],变化的是这个点和父亲的连边的贡献,也就是这条边两侧的点的a[i]之和的差值. t=1的时候，顺着链上的思路,我们先随便找一个点为根建树，将有边直接相连的两个点的b[i]作差.设x的父亲为prt[x],以x为根的子树中所有a[i]之和为sum(x), SUM=a[1]+a[2]+...+a[n-1]+a[n]，那么b[x]-b[prt[x]]=(SUM-sum(x))-sum(x). 同链的情况一样,得到n-1个式子，将树根的b[i]也列出式子,可以求出全部a[i]之和,然后就可以根据之前的式子推出所有的a[i],和链的做法类似，不再赘述.
测试点1：求树上任意两点间的距离，直接换根dfs就好，这样每次的深度就是u到root的距离。Theta (n^2) 遍历所有点对
2 3 4：高斯消元，记得开double，最后%.0lf输出 （考场上板子记不熟，边推边打边调 肝了我30分钟）
正解非常帅，但是先留个坑去写插头dp了，晚上填坑。
C. 题(problem)
打完T2的40pts来看这题。
题意很熟悉emm visit!
只不过要回到(0,0)，这样我们就用老套路成功干掉了opt==0的25pts
$C_n^i imes C_i^{ frac {i} {2} } imes C_{n-i}^{ frac {n-i} {2} }$
对于opt==1，我们把向x正半轴走视为+1，反之则-1，则在任何位时间前缀和>=0，显然是个卡特兰数。
$ans=Catalan( frac {n} {2} )$ $Catalan(n)=C_{2n}^n-C_{2n}^{n-1}$