部分题解合集

题解合集1

懒得分开写咕咕咕

ARC153D

考虑 A 比较小的时候应该怎么做，记 $dp[i][a]$ 表示考虑低 $i$ 位，填的数字是 $a$，低 $i$ 位的贡献。

转移枚举下一位填什么，计算答案的方式是统计当前位上每个数字各有多少个。因为有进位所以这还比较麻烦

如果从小到大枚举 $a$，那么进位的计算是容易的，维护一个 $cnt$ 数组即可，按低 $i$ 位排序后双指针即可。

我们可以以 $O(A)$ 的复杂度计算答案。

事实上我们发现我们并不需要记录所有的 $a$，对于进位状况相同的 $a$，我们只需要它的最小值，而进位状况是 $O(2\times10^5)$ 级别的，改变状态，记 $dp[i][j]$ 表示考虑低 $i$ 位，一共有 $j$ 个数进位，只考虑低 $i$ 位时答案的最小值。

显然只会是低 $i$ 位最小的 $j$ 个数进位，答案计算式类似的。

这道题的优化本质上是分析了转移所需信息，利用问题的最优子结构性质，构造出了更加精简的状态。

ARC154D

$1$ 是比较特殊的数，如果找到了 $1$，设它的位置为 $v$，我们就可以在 $O(n\log n)$ 的时间内对其它数排好序，具体的，考虑构造一个下标序列 $a$，使得 $p_{a_i}=i$，以插入的方式来构造。二分下一个元素 $x$ 插入的位置 $i$，询问 $(v,a_i,x)$，如果答案为 Yes，那么 $x$ 应该插入在 $a_i$ 左边，否则为右边。

怎么找 $1$，对于 $1$，询问 自身+自身>其它数 都是不成立的，有一个比较容易的 $n^2$ 方式。考虑到对于 $[1,n]$ 中的任意一个数，有一半的数在询问 自身+自身>某个其它的数 的结果都是 Yes，因此可以排除一半的数，且留下来的数仍然是 $[k,n]$ 的形式，注意那个其它的数需要拿出来。做 $\log n$ 次拿出 $\log n$ 个数，以 $\log^2n$ 的复杂度检查剩下的数即可，总复杂度 $O(n\log n + n +\log^2 n)$

P5156

考虑一个逆序对，它会消失当且仅当某个端点被选择，所以排好序的必要条件是对于所有的逆序对，至少需要选择两个端点中的一个，这个条件也是充分的，因为只要存在逆序对就会被交换。

一种思路是设 $dp[i][j]$ 表示考虑前 $i$ 个元素，没有被选择的最大的元素是 $j$，且前 $i$ 个元素均合法的最小子集大小。考虑转移，一个元素 $a_i$ 选当然没有问题，不选当且仅当 $a_i>j$，否则存在一个两端都没被选的逆序对。

然后把转移图画出来发现不选的元素就是个 LIS，实际上想的时候还想了线段树去优化原式的转移emmm。

从子集的补集逆向考虑，容易发现它们之间不存在逆序对，因此子集的补集是单调的。

因此问题变成了求第字典序 $K$ 大的 LIS，很简单了。

P4187

考虑一种结果能被构造的充要条件——存在一段长度为 $k$ 的颜色相同子段。

必要性显然，充分性考虑用构造法证明，具体的，记 $a_i$ 表示 $i$ 的颜色，颜色相同的子段为 $[l,l+k)$。记 $P(c,l)$ 表示用 $c$ 颜色涂区间 $[l,l+k)$。依次进行如下操作： $P(a_1,1),P(a_2,2)\cdots P(l-1,a_{l-1}),P(n-k+1,a_n),P(n-k,a_{n-1})\cdots P(l+1,a_{l+k}),P(l,a_{l})$。

枚举第一个长度为 $k$ 的区间的左端点 $i$，记 $[1,i]$ 不出现连续长度为 $k$ 的子串，且最后一个位置不能和下一个位置相同的涂色方案数为 $g_i$

则总方案数为 $\sum\limits_{i=k}^nm^{n-k+1}g_{i-1}$

考虑 $g_i$ 的转移，不妨枚举最后一个位置的连续长度，得到 $g_i=(m-1)\sum\limits_{j=\max(0,i-k+1)}g_j$。

简单前缀和。

为什么是 $m-1$：钦定了最后一个位置不能和下一个位置相同。

另一种思考方式是考虑统计不合法的方案总数，答案就是 $m^n-f_i$。其中 $f_i$ 表示长度为 $i$ 的段，不出现连续长度为 $k$ 的子串的方案数，对于 $i<k,f_i=m^i$，否则转移和 $g$ 相同。

P7152

考虑对生成后的串 DP，设 $dp[i][c]$ 表示考虑到生成后的串的前 $i$ 个，在 $i$ 处和 $i+1$ 处被分开了，$i$ 所属的段开头(原串结尾)为 $c$ 的方案总数。

以下的串无特别说明均指被生成的串，也就是输入的那个串。

$dp[i]$ 的转移枚举起始位置 $j$ 以及对应的 $j$ 所属的段的开头字符 $c_1$，以及 $j+1,i$ 位置的取值 $c_2,c_3$，转移的要求是 $c_1=c_3$，$dp[i]$ 的第二维下标是 $c_2$，转移的额外系数也是容易计算的，不妨设它为 $w(j+1,i,c_2,c_3)$，一次转移就是 $dp[j][c_1]\times w(j+1,i,c_2,c_3)$，由于 $c_1,c_2,c_3$ 的取值都是常数种，我们干脆将它们视作一个参数 $c$，得到转移结果为 $b(j,i,c)$。

因为 $\sum\limits_j b(j,i,c)$ 对 $i$ 有比较好的转移性质，所以考虑维护所有 $c$ 的 $B_c(i)=\sum\limits_{j} b(j,i,c)$

不难发现 $b(j,i+1,c)=\sum\limits_{c_0} k_{c_0}b(j,i,c_0)$，将这个转移带进 $B_c(i)$ 里去，得到 $B_c(i+1)=\sum\limits_{c_0}k_{c_0}B_{c_0}(i)$。

能够计算 $B_c(i)$ 了，那么 $dp[i]$ 的计算也就容易了，注意对于 $B_c(i+1)$ 需要补上 $dp[i]$ 的贡献。

另一种思考方式是套路的考虑将下一个字符并入上一段或者新开一段，复杂度一样的，其实本质也是一样的。

P6142

最小值最大二分，然后一棵子树，传上去的长度自然越大越好，设 $dp_u$ 表示 $u$ 子树满足 $k$ 限制的前提下传上去的最大的数是多少，然后问题变成了对于若干个数，需要选一个或两个数配对，满足和不小于 $k$，且剩下的最大（不剩下就是 $0$）。

讨论两种情况

• 不剩下
• 剩下一个

显然剩下的这个数的大小有单调性可以二分，变成不剩下的情况，现在考虑怎么 check 不剩下的情况，偶数个直接最大最小，次大次小配对最优，奇数个必须先拿一个最小的不小于 $k$ 的，再如上配对。

复杂度 $O(n\log^2n)$。

P8194

发现没有 $5$ 的情况是好做的，设 $dp[i]$ 表示考虑前 $i$ 个数字的答案，当某两个可以一起按时 $dp[i]=dp[i-1]+dp[i-2]$，否则 $dp[i]=dp[i-1]$。

对于可以一起按的情况，分按和不按两种情况，不按的方案数是 $dp[i-1]$，按的方案数是 $dp[i-2]*2$，但是由于如果是顺序的，按的情况和不按的情况恰好有 $dp[i-2]$ 中是冲突的（按也能取到这种方案，不按也可以）。减掉即可。

考虑存在同时按四个的情况，这是一件很麻烦的事情，要容斥掉按四个和不按的冲突非常的困难。

不会了，换个角度思考。

考虑判定问题，即给定 $T$ 判断是否能生成 $S$，记 $ok[i]$ 表示只考虑前 $i$ 位能否生成，转移可以从 $i-1,i-2,i-4$ 转移过来。

考虑对判定过程 dp，记录前 $3$ 个位置的具体值，枚举下一个位置的具体值尝试转移，发现还需要记录前 $4$ 个位置判定 dp 的值，发现这样的 dp 恰好是不重不漏的，因为状态中三个具体值不同的显然本质不同，而 dp 值不同的显然也本质不同，所以同一阶段不同状态不重不漏，因此整个 dp 不重不漏。

总复杂度是 $O(n\times9^4\times2^4)$，跑不动，考虑常数优化。

记录三个位置的具体值很浪费，实际上大部分组合都用不到。

如果四个位置 dp 值全是 $0$ 这个状态直接扔掉。如果当最靠前的一个位置的 dp 值为 $0$，那么最后一个数是没有用的，可以压进一个状态里。如果记录的最后三个数不是接下来四个数排列，那么可以认为最后一个位置的 dp 值为 $0$，所以按最后一个位置 dp 值分类，我们的状态数变为了 $8\times 24+8\times 99$。同理对倒数第二个位置的 dp 值再分类讨论可以进一步压缩状态，状态数应该是可以压缩进 $200$ 以内的。

Tricks

• 对于部分序列计数问题，可以考虑对判定过程动态规划，由于转移所需的序列值不同或者判定的动态规划值不同的状态时本质不同的，所以这样的动态规划是不重不漏的。
• 上述动态规划的优化可以通过减小状态空间完成，主要方式是分析判定问题本身的性质以排除不可能对答案产生贡献的状态。

P4649

首先有一个很重要的观察，覆盖奇数条树边的非树边一定要选。

对于覆盖偶数条树边的，如果任意两条非树边覆盖的边集有交，那么一定可以构造出一种合法的路径（参考欧拉子图计数问题）。

因此问题变成选树上若干条无交的路径使得权值和最大。考虑动态规划。

设 $dp[u]$ 表示只考虑 $u$ 的子树里的路径，$u$ 子树内能选出的权值最大值，发现转移是不好做的，于是多记一维 $dp[u][k]$ 表示考虑 $u$ 子树，$u$ 连出了编号为 $k$ 的路径的权值最大值，先不计算 $k$ 的贡献，并要求 $k$ 的一个端点一定在 $u$ 子树内。

转移的时候就是儿子间两两配对，如果知道了儿子配对的方式，那么我们只需要贪心的让每一个配对取最大值转移，当然儿子也可以不配对或者和父亲配对，我们将不配归类到和父亲配对。

发现儿子配对的方式可以直接枚举，计算答案时需要一个 $mp[v_1][v_2]$ 表示 $v_1,v_2$ 儿子配对的最大值，可以枚举 lca 挂在这个点上的每条边统计。

实际上 dfs 枚举配对方式不是必要的，可以状压 dp，更好写。

教训

• vector 用 lower_bound 删点的时候要先排好序。
• dfs 向后枚举配对的循环里不要忘记判掉已经配好对的。

P8290

极差问题考虑枚举一下最大值位置，然后发现答案是关于最大值 $x$ 的一个 $n$ 次多项式。但是需要去重，很麻烦。

对于这种需要满足至少一个取到边界的问题，或者说与最值有关的计数问题，可以考虑容斥，用不限制取到闭区间的方案数，减去一定不满足的方案数——取到开区间的方案数，得到一定取到闭区间的方案数。

或者说正难则反，考虑一定限制下总方案减去不合法方案数。

P4233

竞赛图有一个重要结论：缩点后一定是一条链状的 DAG，每个点向后面所有点有连边。

考虑到求总的哈密顿回路是容易的：枚举一条回路，其它边任意定向，$(n-1)!2^{\frac{n(n-1)-n}{2}}$。我们考虑求出存在哈密顿回路的竞赛图个数。

由以上结论知竞赛图有哈密顿回路的必要条件是必须整体为一个强连通分量，这个条件也是充分的。

归纳的设 $k\le n-1$ 前结论成立，考虑随便从强连通分量里拿一个点出来，删掉其所有边，剩下的一定还是竞赛图——缩点后是一个链状 DAG，然后它到拓扑序最小的点一定有一条边，拓扑序最大的点到它一定有一条边，然后从这个点开始，走拓扑序最小的点。在每个 SCC 内部找到对应的哈密顿回路并将最后一步连向下一个 SCC，最后从拓扑序最大的 SCC 回来即可，因为走到下一步的过程中是可以任意选择下个 SCC 的起点的，所以确定每个 SCC 内部的哈密顿回路之后需要选一个能够回去的位置开始。

直接算强连通的竞赛图数量不好算，考虑容斥，总的图有 $2^{\frac{n(n-1)}{2}}$ 个，对于不联通的图，枚举拓扑序最小的 SCC 大小，不相关的边可以任意定向，从最小的 SCC 连向其它点的边必须同向，设 $f_n$ 表示 $n$ 阶竞赛图强连通的方案数，有：

$$f_n=2^{\frac{n(n-1)}{2}}-\sum_{i=1}^{n-1}\binom{n}{i}2^{\frac{(n-i)(n-i-1)}{2}}f_i$$

设 $g_n=2^{\frac{n(n-1)}{2}}$，改写为：

$$f_n=g_n-\sum_{i=1}^{n-1}\binom{n}{i}g_{n-i}f_i$$

可以分治 NTT 了，但是继续考虑其指数生成函数的形式幂级数 $F,G$。

$$\begin{align} F(x)&=\sum_{n\ge0}\frac{f_nx^n}{n!}\\ &=\sum_{n\ge0}\frac{x^n}{n!}(g_n-\sum_{i=1}^{n-1}\dfrac{n!}{(n-i)!i!}g_{n-i}f_i)\\ &=G(x)-\sum_{i\ge1}\frac{f_ix^i}{i!}\sum_{n\ge1}\frac{g_nx^n}{n!}\\ &=G(x)-(F(x)-1)(G(x)-1)\\ &=-F(x)G(x)-1+2G(x)+F(x) \end{align}$$

然后移项解方程，$F(x)G(x)=2G(x)-1\iff F(x)=\dfrac{-1}{G(x)}+2$。

多项式求逆即可。

对于固定 $n$ 的情况，其实归纳的考虑较小的 case 也是一种策略。

CF1542E2

最开始考虑把两个条件都写出来看能不能容斥，然后发现不行。

考虑枚举第一个条件在哪里满足，也就是两个排列第一次不同的位置，对于逆序对，前面相同的部分逆序对不管，前后跨越的部分也可以不管。然后可以将后面看成一个新的排列做，第一个不同的位置和后面的逆序对个数有差异！具体的，如果 $p$ 为 $x_p$，$q$ 为 $x_q$，那么在该位置 $p$ 比 $q$ 少 $x_q-x_p$ 个逆序对。

后面仍然可以看成一个排列，然后枚举一下 $p$ 比 $q$ 少的数量 $d$，接下来问题就变成了求两个排列逆序对相差多于 $d$ 的方案数。再枚举一下较多那个排列具体有多少个逆序对，另一边是前缀和，基本问题就变成了求 $n$ 阶排列有 $x$ 个逆序对的方案数。

这个基本问题可以动态规划，按位置做不好做，所以按值从小到大做，具体的，设 $dp_{n,x}$ 表示 $n$ 阶排列有 $x$ 的逆序对的方案数，考虑插入下一个 $n+1$，答案还是前缀和。

基本问题在 $O(n^3)$ 内解决了，但是刚刚的过程是 $O(n\times n\times n^2)=O(n^4)$ 的，考虑优化，记 $f_{n,i}$ 表示 $n$ 阶排列 $i$ 个逆序对的方案数，$g$ 为其前缀和，先写式子：

$$\begin{align} Ans&=\sum_{i=1}^nA_n^{i-1}\sum_{d=1}^{n-i}n-i-d+1\sum_{j=d+1}^{\frac{(n-i)(n-i-1)}{2}}f_{n-i,j}g_{n-i,j-d-1}\\ &=\sum_{i=1}^nA_n^{i-1}\sum_{j=0}^{\frac{(n-i)(n-i-1)}{2}}g_{n-i,j}\sum_{d=1}^{n-i}f_{n-i,j+d+1}(n-i-d+1)\\ &=\sum_{i=1}^nA_n^{i-1}\sum_{j=0}^{\frac{(n-i)(n-i-1)}{2}}g_{n-i,j}[(n-i+1)(g_{n-i,j+1+n-i}-g_{n-i,j+1})+\sum_{d=1}^{n-i}f_{n-i,j+d+1}(-d)]\\ &=\sum_{i=1}^nA_n^{i-1}\sum_{j=0}^{\frac{(n-i)(n-i-1)}{2}}g_{n-i,j}[(n-i+1)(g_{n-i,j+1+n-i}-g_{n-i,j+1})-\sum_{d=1}^{n-i}df_{n-i,j+d+1}]\\ &=\sum_{i=1}^nA_n^{i-1}\sum_{j=0}^{\frac{(n-i)(n-i-1)}{2}}g_{n-i,j}[(n-i+1+j+1)(g_{n-i,j+1+n-i}-g_{n-i,j+1})-\sum_{d=1}^{n-i}(j+d+1)f_{n-i,j+d+1}]\\ \end{align}$$

后面那个 $\sum$ 也是可以前缀和的。

变成 $O(n^3)$。

CF798D

先考虑了每个数和中位数、平均数的大小关系来决定是否选择。然后想能不能构造 $c=a+b$ 在 $c$ 上先贪心选择然后再调整让不满足条件的那个数组满足条件。都失败了。

两个数组都是无序的不好考虑，将 $a$ 降序排列。考虑钦定 $b$ 满足条件并尽可能使 $a$ 满足条件。如果 $n$ 为奇数，我们可以选择 $a_1$，然后将后面的两两分组。每一组选择 $b$ 较大的那一个，这样 $b$ 一定满足条件。然后又因为我们选了 $a_1$，$a_1$ 和第一组配对，第一组的 $a$ 和第二组的 $a$ 配对，然后 $a$ 也满足条件。

偶数同理。

构造完了，这种贪心按对决策的思路很有学习价值，题目中的选一半也提示了这种方式。

ARC156C

给树上每个点一个权值，构造一种方案使得树上所有路径的权值和编号构成序列的 LCS 的最大值最小。

首先放到链上去做，发现长度最大为 $1$，并且方案固定——逆序，猜想总能构造出长度为 $1$ 的解。应该需要利用逆序的性质。

想的是随便定一个根从下往上构造，叶子就优先连上去，每个点只会往上传 1-2 个，然后 $n$ 为奇数的时候在根上遇到了麻烦（这个麻烦是因为没有注意到两个互换的点即使经过了一个不动点贡献也不会增加出现的。）

然后发现类似的思路都处理不了拉一条长链的情况。

于是考虑找一些点集互换，拉出一半的点来，两边各自按深度排序，对应互换填进去，这样对于两边的任意一条路径经过的一定是倒序的另一边，最大长度为 $1$。但是注意到有可能从一个点集经过另一个点集再回到第一个点集，这样就不行了，所以要找到重心按子树大小排序后划分，这样能保证不存在上述情况。

其实有更简单的方式，每次选两个叶子连上去，一直这么做直到只剩下一个，每次选完叶子后因为如果这一对点要算进 LCS 里面就必须选了一个之后马上跳到另一个，中间路径的所有贡献都将被忽略，如果剩余部分同样这么构造就没问题。

这种方式是一种典型的归纳思考的方式，需要学习。

最开始思路出现问题的一个重要原因还是简单的认为只要一条路径覆盖了被交换的点，这一对点就会贡献，实际上还有一个顺序问题。

有时候重新审视题目是很有必要的。

ARC156D

最开始想到逐位确定答案，然后发现只能确定最末位，对于高位由于各个位数复杂的贡献不好算。

然后发现这个是异或问题，而且等价的方案是可重排列，大概率是偶数，于是想到分析有贡献的方案。

运用卢卡斯定理可以知道，一个方案有贡献当且仅当可以被划分成 $k$ 的子集，而且不能有交，也就是对于 $k$ 中的每一个二进制位，都只能有一个数选择它。问题变成了求 $\sum a_{p_i}2^{k_i}$ 的，注意到 $a$ 的值域是 $1000$，也就是说如果过了 $11$ 个二进制位之后前面的数就没用了，所以考虑设 $dp_{i,k}$ 表示考虑到二进制下第 $i$ 位，这一位上的值为 $k$ 的方案数，转移枚举下一个二进制位选哪一个，并和前一位的进位加起来。答案的统计可以在移动最低位时进行，最开始我直接用此时的 dp 出来的方案数作为贡献计算，然后错了。看题解后才注意到此时的 dp 值并不是实际上这一位为这个值的方案数， 还需要考虑后面的选择对此时方案数的贡献。于是当 $k$ 接下来的二进制位还有 $1$ 时，只有在 $n$ 为奇数时才贡献，如果 $k$ 的所有二进制位都被考虑完了，后面才不会有更多的选择贡献到当前的方案数。

教训

• 计数类的问题，如果要在动态规划的过程中计算贡献，一定要考虑之后的选择对当前方案数的影响——当前计算出的 dp 值并不是最终的方案数。

ARC157C

值的平方，拆成有序对的贡献，考虑一段 YY 能和前面的哪些配对，对于靠前的那个 Y 统计，实际上需要算的是从 $(1,1)$ 到该位置的所有路径中有几个 YY，很简单的动态规划。

ARC157D

由于划分是一行一列的划分，又因为每一个格子都是相等的，所以每一列也是相等的。

确定了一列具体有几个之后，每一列划分的位置都在一段区间摇摆且不交，而且对于任何一种划分位置选择，对行的划分都是等价的，于是枚举合法的一列的个数，求出列划分方案数。然后再求对应的行划分方案数乘起来就行。行划分方案在确定了列划分之后，每个可能的划分位置所在区域都不交。

算最边界的时候不能浮动，只能取最外面，不能乘上其贡献。

HDU6801

设 $q=1-p$。

最开始想枚举圈数，算第 $c$ 个在第 $t$ 圈第 $i$ 个被删的概率，然后想直接算一个组合数的概率。但是不知道具体经过了多少次选择，而且组合数和 $t$ 有关很丑陋，于是没考虑。

实际上，这类题有一个 Trick，可以不真正的删掉一个点，而是给它打标记，最后算有多少个打了标记，于是算概率就可以不用组合数，可以考虑每一个点，它被打标记的概率是 $1-q^t$ 或者 $1-q^{t+1}$，然后就是选 $i-1$ 个点被打标记然后钦定第 $c$ 个在第 $t$ 圈第一次打标记的概率。

或者说，我们不去关心每一个具体在 $t$ 圈中的哪一圈被删除，只关心 $t$ 圈后它是否存在，存在的概率是 $q^t$，补集就是不存在的情况。

于是记 $a_i$ 表示第 $c$ 个在第 $i$ 次删除操作中被删除，$t$ 从 $1$ 开始不好，让它从 $0$ 开始：

$$a_i=pq^{t}\sum_{t\ge0}((q^{t+1}+(1-q^{t+1})x))^{c-1}(q^{t}+(1-q^{t})x)^{n-c}[x^{i-1}]$$

考虑 $a$ 的生成函数 $A(x)$：

$$A(x)=p\sum_{t\ge0}q^t((q^{t+1}+(1-q^{t+1})x))^{c-1}(q^{t}+(1-q^{t})x)^{n-c}$$

那个 $1-q^t$ 和 $1-q^{t+1}$ 如果暴力枚举二项式次数拆开，在第一次拆分的时候是合并不了的，会给后面的计算带来很大麻烦，可以把 $q^t$ 提出来将二项式稍微简化一些。

$$\begin{align} A(x)&=p\sum_{t\ge0}q^t(q^{t+1}+(1-q^{t+1})x)^{c-1}(q^{t}+(1-q^{t})x)^{n-c}\\ &=p\sum_{t\ge0}q^t(q^{t+1}(1-x)+x)^{c-1}(q^{t}(1-x)+x)^{n-c}\\ &=p\sum_{i=0}^{c-1}\sum_{j=0}^{n-c}\binom{c-1}{i}\binom{n-c}{j}\sum_{t\ge0}q^t(q^{t+1}(1-x))^ix^{c-1-i}(q^{t}(1-x))^jx^{n-c-j}\\ &=p\sum_{i=0}^{c-1}\sum_{j=0}^{n-c}\binom{c-1}{i}\binom{n-c}{j}\sum_{t\ge0}q^iq^{t(i+j+1)}(1-x)^{i+j}x^{n-1-i-j}\\ &=p\sum_{i=0}^{c-1}\sum_{j=0}^{n-c}\binom{c-1}{i}\binom{n-c}{j}q^i(1-x)^{i+j}x^{n-1-i-j}\sum_{t\ge0}q^{t(i+j+1)}\\ &=p\sum_{i=0}^{c-1}\sum_{j=0}^{n-c}\binom{c-1}{i}\binom{n-c}{j}q^i(1-x)^{i+j}x^{n-1-i-j}\dfrac{1}{1-q^{i+j+1}}\\ &=p\sum_{k=0}^{n-1}(1-x)^{k}x^{n-1-k}\dfrac{1}{1-q^{k+1}}\sum_{i=0}^{k}\binom{c-1}{i}\binom{n-c}{k-i}q^i\\ \end{align}$$

记一个 $f_k=\frac{1}{1-q^{k+1}}\sum\limits_{i=0}^{k}\binom{c-1}{i}\binom{n-c}{k-i}q^i$，$f_k$ 可以卷：

$f=a * b,a_i=\binom{c-1}{i}q^i,b_i=\binom{n-c}{k-i}$，注意两项各自的边界。

再来推：

$$\begin{align} A(x)&=p\sum_{k=0}^{n-1}(1-x)^{k}x^{n-1-k}f_k\\ &=p\sum_{k=0}^{n-1}x^{n-k-1}f_k\sum_{i=0}^k\binom{k}{i}(-1)^ix^i\\ &=p\sum_{k=0}^{n-1}x^kf_{n-k-1}\sum_{i=0}^{n-k-1}\binom{n-k-1}{i}x^i(-1)^i,(k\leftarrow n-1-k)\\ &=p\sum_{k=0}^{n-1}x^kf_{n-k-1}\frac{(n-k-1)!}{(n-(k+i)-1)!}\sum_{i=0}^{n-k-1}\frac{1}{i!}x^i(-1)^i\\ \end{align}$$

然后也可以卷了。

另一种思考方式是动态规划，设 $f(n,i,c)$ 表示第 $c$ 个在还剩 $n$ 个情况下被第 $i$ 次删掉的概率，转移可以枚举下一次删掉的是哪一个：

$$f(n,i,c)=\frac{p}{1-q^n}([i=1]q^{c-1}+\sum_{j=1}^{c-1}q^{j-1}f(n-1,i-1,c-j)+\sum_{j=c+1}^nq^{j-1}f(n-1,i-1,n+c-j))$$

由于是要对每个 $i$ 算，所以状态数是 $O(n^3)$ 的，跑不掉，会死掉的。

考虑先绕到 $c=1$ 然后再一圈一圈弄，记 $f(n,i)$ 表示还剩 $n$ 个，第一个在第 $i$ 次被删掉的概率，先考虑怎么用 $f(n,i)$ 算答案 $a_i$。

$$a_i=\sum_{j=0}^{i-1}p^jq^{c-1-j}\binom{c-1}{j}f(n-j,i-j)$$

然后可以卷，于是问题变成了算 $f(n-j,i-j)$。太麻烦了，先咕咕咕了。

P5401

减法卷积

解决形如 $f_i=\sum\limits_{j=i}a_jb_{j-i}$ 的卷积。

教训

• 推式子的时候不要漏了 $-1$ 项和组合数项。
• 算卷积的时候，由于习惯用 vector 封装，复用 vector 的时候一定要把后面的无用项设成 $0$，乘法返回的 vector 后面是有无用项的，原来用过的因子项数组复用时也要小心。
• multi 函数里面记得要 resize。