星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

计数与期望简单做题笔记

posted on 2019-01-11 20:40:08 | under Diary |

专题写笔记比较适合。考试就不这么写了吧,大概。
这个写的可能比较简单,因为我全都不会做只能看网上题解

数论计数

$[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)$ 预处理第一类斯特林数,去看肖大佬博客或者这个

$[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$ 。