计数与期望简单做题笔记

专题写笔记比较适合。考试就不这么写了吧，大概。 这个写的可能比较简单~~，因为我全都不会做只能看网上题解~~ ## 数论计数 ### $[loj6202]$叶氏筛法（已填坑） $f(i)=i$的$Min\_25$筛裸题。 只要筛质数。 ### $[spoj34096]divcntk$（已填坑） $f(i)=1$的$Min\_25$筛裸题。 当然似乎也可以定个值，不过无所谓，而且那样筛起来还挺麻烦，不如在求$S$的时候一并算来得方便。 ### $[loj572]\rm Misaka\ Network$与求和（已填坑） 很有意思，需要理解$Min\_25$筛究竟是在干啥，才能方便地计算贡献。 ~~用来复习莫比乌斯函数的性质题。~~ 这里的$f$是原题的$f^k$。 $$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^nf'((i,j))^k\\&=\sum_{p=1}^n\sum_{i=1}^n\sum_{j=1}^nf'(p)^k[(i,j)==p]\\&=\sum_{p=1}^n\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}f'(p)^k[(i,j)==1]\\&=\sum_{p=1}^nf'(p)^k\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{d\vert (i,j)}\mu(d)\\&=\sum_{p=1}^nf(p)\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\lfloor\frac{n}{dp}\rfloor^2\\&=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2\sum_{p\vert T}f(p)\mu(\lfloor\frac{T}{p}\rfloor)\\&=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2(f\ast\mu)(T)\end{aligned}$$ 前面那部分整除分块，问题主要是后面部分的快速计算。 虽然很容易想到杜教筛，但$f\ast\mu$的前缀和并不好算，因此我们需要改一下，让$f\ast\mu$变成杜教筛的$f$。 $$(f\ast\mu)\ast1=f\ast\epsilon=f$$ 因此我们设$H(n)=\sum_{i=1}^n(f\ast\mu)(i)$，又因为杜教筛里的$g$是$1$函数，那么 $$H(n)=F(n)-\sum_{i=2}^nH(\lfloor\frac{n}{i}\rfloor)$$ 因此$H$我们可以用杜教筛求到，那么问题转化为快速计算$F(n)=\sum_{i=1}^nf(i)$。 这个东西涉及到了质因子，因此非常适合用$Min\_25$筛计算，因为它求$S$的部分就是在枚举质因子，因此我们算当前递归位置的答案$S(n,j)$的时候，那个次大质因子是可以知道的。 首先质数的$f(x)=1$，所以求$g$就是求质数个数。 我们考虑$Min\_25$筛求合数部分的式子： $$S(n,j)=g(n,\vert P\vert)-g(P_j-1,j-1)/\sum_{i=1}^{j-1}f(P_i)+\sum_{i=j}^{P_i^2\le n}\sum_{k=1}^{P_i^{k+1}\le n}(F(P_i^k)S(\frac{n}{P_i^k},i+1)+F(P_i^{k+1}))$$ 可以注意到，虽然这里枚举的是一坨数，但实际上我们求$S$是一个递归的过程，而实际上我们运用积性函数的性质去递归的时候，在当前递归之前我们已经乘了一坨数，也就是其实质数也并不是质数，而且并不是只有一个质因子的数（这点可以观察它的过程），那么它们都是有贡献的，而且贡献就是$P_{j-1}$。 于是我们只需要在筛的过程中，把贡献乘上去就可以了。注意$F(P_i^k)S(\frac{n}{P_i^k},i+1)$这一块不用加贡献，因为这个贡献在之后加。之后那个因为质因子个数$\ge2$，因此贡献是$P_i$。 虽然我觉得这玩意儿复杂度很不靠谱，但$loj$的题解说是$O(n^{1-\omega})$的，那就是吧。 似乎因为一直是整除分块的运算，$g$可以直接预处理。 ### $[Simulation1.25]easymath$（已填坑） $\rm orz\ Gromah.$ 题意：求 $$\sum_{i=1}^n\mu(in),n\le 10^9$$ ## 容斥原理与状态压缩 ### $[bzoj4671]$异或图 考虑正着的“连通”这个条件不知道怎么计数，不如跟一般连通图计数一样用容斥解决问题。因为每个点是不同的，所以我们用斯特林数来枚举划分。 考虑划分的每一个集合内部连边任意，但是不同集合之间一定没有边。 令$f_i$表示一个图至少有$i$个连通块时的容斥系数，考虑对于一个有$m$个连通块的图，它的容斥系数关系式是： $$\sum_{i=1}^m\begin{Bmatrix}m\\i\end{Bmatrix}f_i=[m==1]$$ 斯特林反演一下可以得出 $$\sum_{i=1}^m(-1)^{m-i}\begin{bmatrix}m\\i\end{bmatrix}[i==1]=f_m$$ $$f_m=(-1)^{m-1}\begin{bmatrix}m\\1\end{bmatrix}=(-1)^{m-1}(m-1)!$$ 最后一步的转换似乎是环排列数。 然后现在问题就是，在$s$个边集中，有多少种方案使得各个划分之间连边的异或和为$0$。 我们把每条边（为了方便把划分间的任意点对都算作边）当作向量中的一维，然后把每个边集对应的向量插到线性基里，那么由于线性基内部元素是线性无关的，那么自由元显然都能通过与线性基内元素异或成$0$向量。也就是说假设线性基内元素为$x$，总向量个数为$y$，那么选择的方案数就是$2^{y-x}$。 这个算法的时间复杂度大概是$O(Bell(n)(n^2+s\log^2s))$，大概也就是$O(pass)$吧。 ### $[ARC093F]Dark\ Horse$ 丢人，一点思路都没有。 首先你要发现放在哪个位置其实是无所谓的，因为你可以把比赛过程看成一棵满二叉树（这个$yy$一下就知道了），那么每个结点的两个儿子转一下是不影响答案的。 那么我们钦定编号为$1$的人在一号位置，最后只要$\times 2^n$就可以了。 然后因为直接算“不在”不好算，容斥一下可以变成求当前某些区间$(\in[2],[3,4],[5,8],\cdots)$的最小值都是那$m$个数中的一些的方案数，这个可以用个$dp[i][S]$去算，表示填到第$i$个最小值，之前填了最小值区间的状态为$S$，从大到小填数就可以了。 至于怎么填，首先这个数可以不作为最小值放在之后的里面配，如果作为最小值填到一个新区间里，那我们可以将当前还没配（就是上次填的数中剩下的和这次填的中本来就有的）的数统计一下，然后每次枚举一个新区间放最小数的时候，可以用排列算一下方案，就做完了。 ### $[ZJOI2016]$小星星（已填坑） 一道小清新容斥题。 因为不能重复，考虑一个$O(n^33^n)$的$dp[u][i][S]$表示$u$号点映射$i$号点在图上映射点集为$S$。这个转移就很显然，也显然会$T$。 考虑我们$O(n^3)$的$DP$如果映射出现重复，那么意味着映射的点集大小不是$n$。 那么我们考虑按点集容斥，枚举点集$S$表示映射的点集强制**至多**为$S$，做一遍树形$DP$，容斥系数就是$(-1)^{\vert S\vert}$？ ### $[bzoj3622]$已经没有什么好害怕的了 对自己的$DP$不够自信啊$\cdots\cdots$ 首先$\ge k$的显然比$=k$好算，因为满足了$=k$之后可以任意排。 然后这个用一个$dp[i][j]$表示前$i$个数中选出来$j$个满足$>$对应$b_i$这个条件的数的方案数。 转移很显然，就枚举当前数选不选就可以了。注意预处理每个数比几个数大。 $dp[n][i](n-i)!$就是$\ge i$的方案数，之后我们考虑怎么容斥。 对于每个$=j$的方案，它在$\ge i$的方案中被算了$\binom{j}{i}$次，因为你可以任选$i$个数；于是我们设$f[i]$表示$=i$个的方案数，则 $$f[i]=dp[n][i]-\sum_{j=i+1}^n\binom{j}{i}f[j]$$ ### $[Simulation1.20]tree$（已填坑） 题意：给定一棵树，每条边有权值$val_i$，有$q$个修改，每个修改改一条边的权值。$val_i\le 10^6,q\le 100,n\le 10^5$。 在每次修改后及全部修改前，求树上满足路径$gcd=1$的点对数。 这题的$idea$就是，发现偏序集容斥之后，就直接上莫比乌斯反演。 考虑求$f(k)=gcd==k$不太方便，可以求$g(k)=gcd\vert k$的方案数。 $$f(n)=\sum_{n\vert d}\mu(d)g(\frac{d}{n})$$ 因为要求$f(1)$，因此$n=1$，$f(n)=\sum_{d=1}^n\mu(d)g(d)$。 考虑$g$怎么求，对于没有修改的情况，我们直接对每个$\mu(d)$有值的$d$，把所有权值是它倍数的边提出来，直接用可撤销并查集去维护答案（显然只有连通才能保证$gcd$）。每条边只会进入$2^c$个$d$，其中$c$指的是不同质因子个数，$val_i\le 10^6$时最大是$7$。 如果有修改，我们一开始先不把被修改的边放进并查集，对于每一个$d$我们先枚举时间，再枚举**有效修改**（否则每个修改不止$2^c$次出现，复杂度就错了），把这些修改放进去算当前时间的答案。注意每个时间最后都要**全盘撤销，因为有些边在不同时间的权值不同**。 时间复杂度应该是$O(\frac{n\sqrt n}{\ln\sqrt n}+(n+q^2)2^c\log n)$，实现细节比较多，否则会假。 ### $[PKUWC2018]$猎人杀 ~~说到$\sout{PKUWC}$，我就想起了斗地主，今年年初，九条可怜的地主斗即将~~ 首先这题比较难考虑的是因为每次死的人都不同，因此分母不同不好计算期望。 因此~~不~~可以想到，我们给每个死去的猎人打一个标记，然后如果$rand$到死了的猎人那就再随一次，显然这样与原问题等价。 然而还是不好安排第一个人在最后一个。 考虑容斥~~我不知道为什么会想到容斥~~，我们枚举集合$S$表示**至少**$S$这个集合会在$1$后面死，$W,w_1,all$分别表示$S,1,$全部猎人的权值和，那么$1$最后死的期望就是 $$\sum_{S}(-1)^{\vert S\vert}\sum_{i=0}^\infty (1-\frac{w_1+W}{all})^i\frac{w_1}{all}$$ 先把无限和式收敛一下 $$\sum_{S}(-1)^{\vert S\vert}\frac{1}{1-(1-\frac{w_1+W}{all})}\times\frac{w_1}{all}$$ $$=\sum_{S}(-1)^{\vert S\vert}\frac{w_1}{w_1+W}$$ 这个式子直接算显然是不好做的，但是我们可以发现因为$W=\sum_{i\in S}w_i$，那么对于每个$W$，它的系数应该是 $$\prod_{i=1}^n(1-x^{w_i})$$ 的$x^W$那一项的系数。这个东西类似于背包，可以进行分治$FFT$。 ### $[2.24\mathrm{simu}]tree$ ## $DP$计数 ### $[AGC002F]Leftmost\ Ball$ 这题真的不难，但我网上题解真的看不懂。知道结论了我还是不会做。 首先我们可以发现一个结论就是如果从左到右那么$0$球数量一定不少于颜色数量。 有了这个我们就很好$DP$了，设$dp[i][j]$表示用了$i$个零球$j$种颜色，然后每次要么加一个$0$球，要么加一个颜色，加颜色的话可以用组合数计算一下。表示在接下来的空位中我们怎么选。空位是相互独立的所以这里选啥不影响之后的空位整体还是那么多。 组合数大概是$\binom{n-i+(n-(j-1))(k-1)-1}{k-2}$，注意这里必须要放一个当前颜色的球因此只能选$k-2$个。还要注意我们要选颜色，当然也可以在最后乘阶乘。 ### $[AGC013E]Placing\ Squares$ 不太懂网上为啥要把题面转成$\rm WerKeyTom$那种形式。原题面不是挺好的么$\cdots\cdots$ 这道题运用了**平方处理**这个很重要的技巧，但我忘了。所以也没办法。 首先这个贡献看起来很简单，但我们发现如果我们要进行与边长相关的$DP$，复杂度会达到$O(n^2)$级别，谁都救不了。 于是我们考虑在正确计算贡献的情况下转换模型。 考虑一个长度为$n$的区间，我们可以在每两个数之间任意放隔板，但是在那些限制的位置不能放。然后每个被隔板分开的区间（包括首尾）我们都要放也只能放两个**不同**的球，并且每个位置允许放两个球。求这样的方案数。 观察到这个模型是等价的，因为每种划分的贡献是会被算$\prod len_i^2$的，显然在这个模型中每个区间也是独立的，因此我们转化成了一个非常方便$DP$的模型。 设$dp[i][j=0,1,2]$表示当前枚举到第$i$个位置，当前区间放了$j$个球的方案数。 如果$i-1\to i$放隔板，那么上一个区间只有$j=2$才合法，因此无论第$i$个位置放几个球，都只能从$dp[i-1][2]$转移； 如果不放，那么$dp[i][j]$就可以从$dp[i-1][k](k\le j)$的地方转移，其中注意的是$dp[i-1][0]\to dp[i][1]$**要**$\times 2$，因为我们要确保两个球是不同的，并且都可以选。 然后这个做法就是$O(n)$的。显然这个东西可以用矩阵加速转移，但因为有限制不能放隔板的地方，因此我们要在每个限制那里暴力转移一次，然后接着矩阵快速幂。 ### $[NOI2009]$管道取珠 **平方处理**还有另外一种转化方式，就是统计有序对。 对于这道题，我们就是要统计有多少对$(way_a,way_b)$能够得到相同的结果，因为对于每种结果考虑方案数显然非常不方便。 ~~然后我就连普及组$\sout{DP}$都不会了。~~考虑$dp[i][j][k][l]$表示$a$选$i$黑$j$白，$b$选$k$黑$l$白，每次只转移方案相同的。注意到$l$没有什么意义，直接去掉就是$O(n^3)$的了。 ### $[hdu5181]numbers$ 这个题告诉我们推了个性质不能膨胀，你还要接着推下一个。 我琢磨了一下出栈序列，发现一个序列非法当且仅当$x<y<z$这三个数满足顺序是$z,x,y$这样的，因为如果$z$出栈了$x$没出栈$y$必然在$x$上面。 推完了之后我发现可以设$dp[i][j][k]$表示第$i$个数是$j$且前面的最大数是$k$时的方案数，尽管可以通过前缀和达到$O(n^3)$，然而并不能处理限制的问题。 然后实际上之前那个性质可以推成下面这个性质，就是考虑按时间把每个数的进出栈序列弄出来，这玩意儿就是个合法的括号序列，因为我们发现是不可能出现交叉（就是譬如$x<y$，$x$入，$y$入，$x$出这样的），也就是说，我们可以构建一棵树，并且这棵树的每个结点$u$的儿子范围是一个形如$[u,u+x]$的连续区间。 那么我们可以设$dp[u][i]$表示$u$号结点子树大小为$i$的方案数，有一个很显然的转移就是$dp[u][i]=\sum_{k=1}^{i-1} dp[u][k]\times dp[u+k][i-k]$，然后倒着$DP$就可以了。 至于限制实际上就是限制了你的子树大小，那我们在$DP$完一个不合法状态后直接把它设为$0$就可以了。初始值就是$dp[u][1]=1$。 为了方便我们加上一个根$0$，答案就是$dp[0][n+1]$。 ### $[THUWC2017]$随机二分图 这题好像送了$40pts$啊$\cdots\cdots$而且我觉得这个正解根本没有提示，$t=0$的状压$DP$可以做到$O(nm2^n)=O(n^32^n)$（而且实际上状态只能选位数$\le$当前枚举点的，根本跑不满），正解这个是$O(\binom{n}{i}^2m)$的（虽然也跑不满）。 考虑$dp[n][S]$这个状压不方便解决多条边的问题，我们要换一种更方便的，就是$dp[S][T]$表示左边$S$匹配右边$T$的期望。 考虑我们后面两个条件具体增加了什么限制。首先我们正常加边，如果只有一条匹配边那概率就不变，如果$t=1$两条都匹配，概率就少了$\frac14$，如果$t=2$就多了$\frac14$（$\frac12\times\frac12=\frac14$），于是我们把两条边再额外捆绑成有四个点的一条边，概率为$\pm\frac14$就可以了。 实现可以从终态记搜，当然也可以直接用个$\mathrm{map}DP$，只选取能匹配的状态的话效率比较优秀。 ### $[CF889E]Mod\ Mod\ Mod$ 这题第三个方程没看懂，先咕咕咕。 ### $[HNOI2015]$亚瑟王 这个题自己想到了不能按回合$DP$不然就只能状压。 然后就不会做了。 现在没完全理解，咕咕咕。 ### $[fakesky2.17\mathrm{simu}]$寒妖王$(mstking)$ ## 条件意义 就是没用什么方法又是计数题的题，通常是很需要分析题目性质的题。 ### $[ACF2017qualB\ E]Popping\ Balls$ 我一开始看错题以为是首尾都能放，然后一想这个$s,t$毫无意义$\cdots\cdots$ 考虑这个$t$其实可以在一段红球之后再决定，假设我们**剩下**$x$个红球，直接将$t=x+1$可以获得最优答案，并且显然$t>x+1$的决策不如等于时优。 那么我们可以预见最终序列的样子： $$x+(1+b-1)+y+(1+b-2-\alpha)+o$$ 这个式子看起来非常莫名其妙，不过其实也不太难解释： 首先，由于上面的那个结论，我们一开始先取$x$个红球，然后取$1$个蓝球。现在我们剩下$a-x$**个红球，**$b-1$**个蓝球**。$x$的取值范围是$[0,a]$，因此$t$的范围是$[1,a+1]$，其中当$x=0$ 时$t$是$a+1$，依此类推。 接下来你可以发现，无论我们怎么取，当取了$b-1$个球后，$t$就再也没有【哔——】用了，于是我们取$b-1$个球，并且在这$b-1$个球中，我们可以枚举$\alpha$个数表示取$\alpha$个蓝球，$\alpha\in[\max(b-1-(a-x),0),b-1]$。现在我们剩下$a-x-(b-1-\alpha)$**个红球，**$b-1-\alpha$**个蓝球**。 然后我们还可以有个$s$，我们仍然可以在选完一段红球后再来确定$s$。我们假设取了$y$个红球，再取$1$个蓝球。现在我们剩下$a-x-(b-1-\alpha)-y$**个红球，**$b-2-\alpha$**个蓝球**。 那么我们还可以取$b-2-\alpha$个球，$s$也会失效，剩下的取球路线唯一。我们可以枚举$\beta$个数表示$\beta$个蓝球，$\beta\in[\max(b-2-\alpha-(a-x-(b-1-\alpha)-y),0),b-2-\alpha]$。现在我们剩下$a-x-(b-1-\alpha)-y-(b-2-\alpha-\beta)$**个红球，**$b-2-\alpha-\beta$**个蓝球**。~~因为化简没什么意义就不化简了。~~ 那么我们枚举$x$，枚举$\alpha$，枚举$y$，枚举$\beta$，关于放球的计数可以把一种球当隔板用隔板法计算，就可以得到一个$O(n^4)$的做法了。 首先我们发现$\alpha$是非常好优化掉的，可以直接累和，然后根据$x$去掉不合法的状况。 ### $[CF960G]Bandit\ Blues$ 很奇怪的一道强行上斯特林数题。 首先我们可以猜到一个结论：最大数一定会把两边分隔开，于是最大数左边必须要有$a-1$个前缀$\max$，右边必须要有$b-1$个后缀$\max$。 于是我们可以把$n-1$个数分为$a+b-2$组，以每个$\max$的右边（后缀就是左边）到下一个$\max$位置为止分为一组。显然可以发现，只要你能填出这样一个排列，组内可以乱填，假设某组有$x$个数，那么就有$(x-1)!$种填法。 不难发现这是环排列数，也就是$\tiny\begin{bmatrix}x\\1\end{bmatrix}$。 那么考虑组合意义，相当于我们要把$n-1$个数放到$a+b-2$个环里去，也就是$\tiny\begin{bmatrix}n-1\\a+b-2\end{bmatrix}$。注意到还需要把所有环划分到两边，但环是有大小顺序的，因此乘一个组合数$\binom{a+b-2}{a-1}$。 然后需要$O(n\log n)$预处理第一类斯特林数，去看肖大佬博客或者[这个](https://www.luogu.org/blog/teafrogsf/Mathematics)。 ### $[HNOI/AHOI2017]$抛硬币 连这$SB$题都不会做了$\cdots\cdots$ 正向计数不好利用$b-a\le 10000$的性质，考虑反向计数。~~$\sout{Candy}$给出了一个正向计数的解法，好强啊~~ 就是首先$a=b$时，我们发现不合法的方案数就是除了平局以外的所有情况的一半，因为反色后就是另一个人赢；$a>b$时因为$A$数量多了，那么有时候对于一种小$A$赢的情况，将其反色后还是小$A$赢。我们设小$B$抛了$i$个正面朝上的，$A$比$B$多$j$个，那么就要满足$a-i-j>b-i$，即$j<a-b$，就可以有 $$ans=\sum_{i=1}^a\sum_{j=1}^{a-b-1}\binom bi\binom a{i+j}=\sum_{i=1}^a\sum_{j=1}^{a-b-1}\binom b{b-i}\binom a{i+j}$$ 我们考虑它的组合意义，就等同于我们在$a+b$个硬币中取$b+j$个朝上的，然后把前面$b$个中间被选了的给$B$，剩下的给$A$（因为组合数没有顺序），可以发现这样就能考虑所有的$i$的情况。那么就可以变成 $$ans=\sum_{i=1}^{a-b-1}\binom{a+b}{b+j}$$ 这个东西叫做范德蒙德卷积，是一个还算不错的组合数套路。 然后就可以直接算了，注意对$2$的次幂特殊考虑，因为它没有逆元，要在上面除掉。卡常的问题去看别人的博客吧。 ### $[HNOI/AHOI2018]$寻宝游戏 这题好神啊，思维太妙了。 首先我认为这题的结论要发现，应该只能用10分暴力打表，发现有贡献的位运算序列是连续的。 然后来讲讲做法吧。就是如果你把操作序列的$\&$看成$1$，$\vert$看成$0$，就可以得出一个船新的$01$序列。那么对任意一列我们把这一列的序列扣出来，发现如果结尾要是$1$，那么最后一个$\vert 1$要在最后一个$\&0$后面。也就是说我们把最后一位看成最高位，那么操作序列形成的二进制数一定要**小于**这一列的二进制数。那么我们把每一列这个数抠出来排序，找到分界点就可以了，答案就是分界点两个数的差。 至于实现，我参考了$Navi\_Awson$打野的，好强啊。 ## 考虑贡献 ### $[AGC005F]Many\ Easy\sout{Hard}\ Problems$ 这种题一看题解就懂，自己又不会做。好菜啊。 首先，虽然考虑一个点的贡献是正常的想法，但那样多了一点细节，我们不妨考虑一条边的贡献。显然一个连通块大小$=$边数$+1$，而$+1$也就是在每个$k$最后加一个$\binom{n}{k}$就可以了。 考虑每条边把一棵树分成了大小为$x,n-x$的两个部分，那么它产生的贡献就是$\binom{n}{k}-\binom{x}{k}-\binom{n-x}{k}$。 这样只能$O(n^2)$做，可以考虑记一下每个$x$的出现次数$cnt_i$，这个$x$显然就是子树大小。注意每棵子树的$n-x$也算作子树大小，也加到$cnt$里。 为了方便，设$cnt_n=-(n-1)$。因为统计的是边的贡献，不存在子树大小$=n$的情况，而显然$\binom{n}{k}$会出现$n-1$次。 然后问题转化为了对每个$k$,求 $$\begin{aligned}ans_k&=\sum_{i=k}^n-cnt_i\binom{n}{i}\\&=-n!\sum_{(n-i)=0}^{n-k}\frac{cnt_i}{i!(n-i)!}\\&=-n!\sum_{i=0}^{n-k}\frac1{i!}\times\frac{cnt_{n-i}}{(n-i)!}\end{aligned}$$ 直接卷就完事儿了。记得求和上界是$n-k$因此要最后要把卷完的序列反过来。 ### $[PKUWC2019]$你和虚树的故事 这题想了半天一点想法都没有，结果是我看错题面了$\cdots\cdots$ 后来想了一个奇怪做法，不知道是不是真的反正很麻烦，还是来讲讲标算吧。 其实有一个很妙的做法，就是用到点数$-$边数$=1$这个$trick$，可以直接算出每种集合大小对应的贡献和，套个组合数之后，可以$NTT$加速计算。 ## 高斯消元 ### $[BJOI2018]$治疗之雨 其实是道傻题，只是我比它更傻。 考虑直接设$dp[i]$表示剩余生命值为$i$时期望几回合死亡。 $$dp[i]=1+\frac1{m+1}\sum_{j=0}^{\min(i+1,k)}p(j)dp[i+1-j]+\frac m{m+1}\sum_{j=0}^{\min(i,k)}p(j)dp[i-j]$$ $$dp[0]=0,dp[n]=1+\sum_{j=0}^{\min(n,k)}p(n,j)dp[n-j]$$ $$p(j)=\frac{\binom kjm^{k-j}}{(m+1)^k}$$ 其中$p(j)$表示$k$个反甲~~不管了就这么叫吧~~给自己扣了$j$血的概率。注意$0^0=1$。 然后显然可以直接高消。但注意到这个矩阵与下三角非常像，只要倒着消，每次用$i+1$行把$i$行的第$i+1$个数消掉，就变成下三角了。然后直接正着回代即可。 这个题特判非常恶心，有很多情况。 ## 群论 ### $[spoj422]transsp2$ 这个东西既然是$2^x$，那么我们考虑把坐标用二进制表示再拼接起来，那么换位实质上就是把这个二进制数左移动$a$位，这个东西举个例子：$a=2,b=3,(2,7)\to10111\to(7,2)\to11110$，感性理解一下。 把对应的二进制数间连边，答案变为$2^{a+b}-$环的个数。问题又可以等价变形为，有一个长度为$a+b$的环，在环上黑白染色，如果一个环能通过左移$a$位得到另一个环那么称这两个环等价，求环染色方案数。 首先这个置换的循环节大小是$n=\frac{a+b}{(a+b,a)}$循环节个数是$g=(a+b,a)$，但这个不能直接上$Polya$。于是我们把连续的$g$位捆在一起(显然这$g$个数分别位于不同的循环节)，然后上$Polya:$ $$ans=\frac1n\sum_{i=1}^n2^{g^{(i,n)}}$$ 这个玩意儿可以直接上$\mu$，这里不写了，反正化完了就是个$\varphi$。