错位排列计数 （组合意义dp）
题目
给定长度为 \(n\) 的排列,求解其错位排列数
题解
设 \(D_n\) 表示长度为 \(n\) 的排列的错排数,考虑我们已经知道了前 \(n-1\) 个错排数,那么对新加入的这第 \(n\) 个数进行分类讨论
- 直接与前面的数交换,有 \((n-1)\times D_{n-2}\) 种方案
- 放在前面某个数的位置上,那么相当于给原来 \(n-1\) 个数做了错排,有 \((n-1) \times D_{n-1}\) 中方案
所以
这个递推式可以求出其通项,但这不是本博客讨论的范围,读者感兴趣的自行了解即可
NOIP 四校联测 Day1 T2 （组合意义dp）
题目
给定两个排列 \(A,B\),求字典序介于 \(A,B\) 之间的排列最大前缀个数恰好为 \(k\) 的排列的个数
\(|A|,|B|\le 3000\)
题解
首先我们考虑没有字典序的限制要怎么做,设 \(f[i][j]\) 表示倒着往前考虑到第 \(i\) 个数,最大前缀个数为 \(j\) 时的排列的个数,转移时考虑组合意义
\[f[i][j]=f[i-1][j-1]+(i-1)\times f[i-1][j] \]也就是我们当前的 \(i\) 是最小的那个数,我们考虑它如果放在最前面,那么前缀最大值的个数会 \(+1\),否则不会发生改变
考虑正解
一眼丁真,类似数位dp,应该是要进行一个差分的,也就是 \(\ge a\text{数的个数}-\ge b\text{数的个数}\)
于是我们考虑从前到后枚举每一位,以 \(\ge a\text{数的个数}\) 为例,假设 \(i\) 位之前都是相同的,我们枚举每一个在 \(A\) 数组的前 \(i-1\) 个位置没有出现过，而且比 \(a[i]\) 大的数字 \(B\) 填到位置 \(i\) 上
因此前 \(i\) 个位置我们已经填好了，且消除了对后面字典序的限制
考虑 \(1\sim n\) 中没有在前 \(i\) 个位置出现过的数字的集合为 \(S\) ，设我们已经填了的数字的最大值为 \(\text{mx}\) ，则 \(S\) 集合中所有小于 \(\text{mx}\) 的数字，都不会对前缀最大值的个数产生贡献
设前 \(i\) 个位置中，前缀最大值的个数为 \(C\) ，\(S\) 集合中大于 \(\text{mx}\) 的数字个数为 \(D\),那么有我们在 \(i+1\sim n\) 必须整出 \(k-C\) 个前缀最大值才可以
而 \(S\) 集合中小于 \(\text{mx}\) 的数是可以随便填的,所以当前对答案的贡献就是
\[\binom{D}{k-C}\times f[D][k-C] \times (n-i-D)! \]然后把所有 \(i\) 对应的答案加起来就行了,时间复杂度 \(\mathcal{O} (nk)\)
NOIP 四校联测 Day2 构造数组 （辨认无意义的状压dp+组合意义dp）
题目
你现在有一个长度为 \(n\) 的数组 \(a\)。一开始，所有 \(a_i\) 均为 \(0\)。给出一个同样长度为 \(n\) 的目标数组 \(b\)。求有多少种方案，使得通过若干次以下操作，可以让 \(a\) 数组变成 \(b\)。
- 选出两个不同的下标 \(1\leq i<j\leq n\)，并将 \(a_i\) 和 \(a_j\) 同时增加 \(1\)。
两种方案被称之为不同的，当且仅当存在一个 \(x\) 使得一种方案中第 \(x\) 次操作选择的两个下标 \((i,j)\) 与另一种方案中的不同。
\(1\le n\le5~000\)，\(1\leq b_i\le30~000\)，\(\sum b_i\le30~000\)
题解
这道题感觉出的挺好的,部分分给的挺多的,正解是不太好想的,考场上花了好长时间想,最后也没调出来
首先我们可以将这个问题转化成,我现在有 \(\frac{n}{2}\) 个容量为 \(2\) 的桶,然后我要往这些桶里面放东西。
一种朴素的状压dp做法是,考虑设 \(f[i][s]\) 表示考虑到第 \(i\) 个元素,各个桶的放置情况是 \(s\) 时的方案数。
然而我们发现我们其实并不关心每个桶放数的情况,我们只关心放了 \(0\) 个,\(1\) 个,\(2\) 个桶的数的个数,因此我们可以将状态设为 \(f[i][j][k]\) 表示考虑到第 \(i\) 个元素,个数为 \(1\) 的桶有 \(j\) 个,个数为 \(2\) 的桶有 \(k\) 个时的方案数,这样可以推出个数为 \(0\) 的桶的个数,转移时枚举当前元素有多少分给了 \(0\) ,多少分给了 \(1\) ,组合数计算转移即可
更进一步,我们发现知道了个数为 \(2\) 的桶的数量,我们是可以计算出考虑到第 \(i\) 个元素时个数为 \(1\) 的桶的数量的(因为前面的桶一定要全选完,不然没法跟后面的桶配对),转移同上
时间复杂度 \(\mathcal O\left((\sum b_i)^2\right)\)
容斥原理套路于DP
参考本校学长ylxmf2005的博客,容斥原理在dp中有如下的经典应用:
- $\text{一个也没有}=\text{全部都有}-\text{至少一个}+\text{至少两个}-{至少三个}+\cdots $
- \(\text{所有限制}=\text{没有限制}-\text{一个限制}+\text{两个限制}-\cdots\)
- \(\text{恰好有}k\text{个}=\text{至少有}k\text{个}-\binom{k+1}{k}\text{至少有}k+1\text{个}+\binom{k+2}{k}\text{至少有}k+2\text{个}-\cdots\)
- \(\text{min-max容斥}\) \(\max(s)=\sum_{t\subset s}(-1)^{|t|-1}\min(t)\)
一般容斥原理直接暴力做的复杂度是 \(\mathcal O(n2^n)\),需要我们用dp或者多项式进行优化
P5664 [CSP-S2019] Emiya 家今天的饭 （容斥原理套路1）
题解
首先,如果直接考虑本题合法的方案数,我们发现题目中的限制有些过于多了,正难则反,考虑容斥
所以我们可以钦定一定有某一种食材超过了限制,那么答案就是总的方案数减去不合法的方案数。设 \(f[i][j][k]\) 表示考虑到第 \(i\) 种烹饪方法,超限食材使用了 \(j\) 次,其它食材使用了 \(k\) 次的方案数; \(\text{sum}\) 表示第 \(i\) 种烹饪方式所能做的菜的种类的和。那么枚举当前考虑的食材是 \(c\) ,那么有转移
\[f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k]\times a[i][c]+f[i-1][j][k-1]\times (\text{sum}[i]-a[i][c]) \]不合法的方案数就是
\[\sum_{j> k} f[i][j][k] \]设 \(g[i][j]\) 表示考虑到第 \(i\) 种烹饪方式,使用了 \(j\) 种食材时的总方案数,转移为
\[g[i][j]=g[i-1][j]+\text{sum}[i]\times g[i-1][j-1] \]于是
\[\sum_{i=1}^{k} g[n][i] \]就是我们的总方案数
综合来看,我们目前的时间复杂度是 \(\mathcal O(n^3m)\) 的,无法通过本题,于是考虑优化
这就是这道题最经典的地方了,我们发现对于 \(j,k\) 这两维,我们最后统计答案的时候关心的仅仅只是它们的相对大小关系,因此我们更改状态为 \(f[i][j]\) 表示考虑到第 \(i\) 种烹饪方式,钦定的使用数量最多的那一种食材相对其它食材的总和的差为 \(j\),那么转移就变成了
\[f[i][j]=f[i-1][j]+f[i][j-1]\times a[i][c]+f[i-1][j+1]\times (\text{sum}[i]-a[i][c]) \]于是时间复杂度就降为了 \(\mathcal O(n^2m)\)
P1450 [HAOI2008] 硬币购物 （容斥原理套路1）
题目
共有 \(4\) 种硬币。面值分别为 \(c_1,c_2,c_3,c_4\)。
某人去商店买东西，去了 \(n\) 次，对于每次购买，他带了 \(d_i\) 枚 \(i\) 种硬币，想购买 \(s\) 的价值的东西。请问每次有多少种付款方法。
\(1 \leq c_i, d_i, s \leq 10^5\)，\(1 \leq n \leq 1000\)。
题解
与上一道题同理,直接利用分组背包计算合法的方案数肯定是T飞了的,所以同样考虑容斥
我们分别钦定有 \(1\) 种, \(2\) 种, \(3\) 种 ,\(4\) 种硬币超过了限定了数量,没有限定的硬币随便选,假设当前选择的超限硬币组成的集合为 \(S\) 那么我们每次就相当于做一个背包容量为 \(s-\sum_{i\in S}(d_i+1)\times c_i\) 的完全背包,容斥一下,奇加偶减即可,这个时间复杂度就降为了 \(\mathcal O(n)\) ,采用预处理完全背包的做法的话带一个 \(4\) 的常数,不预处理也是可以通过的
BZOJ3622 已经没什么好害怕的了 （容斥原理套路3）
题目
给定 \(a\),\(b\) 两个长度均为 \(n\) 的数列,我们现在要对它们进行两两配对,问配对后 \(a\) 比 \(b\) 大的个数比 \(b\) 比 \(a\) 大的个数多 \(k\) 组的方案数
\(n\le 5000\)
题解
无序的序列过于丑陋,所以我们先要对两个序列先进行一个排序
设 \(p[i]\) 表示使得 \(b[j]<a[i]\) 最大的 \(j\)
同样与上一题类似,设 \(f[i][j]\) 表示考虑到 \(a\) 序列的第 \(i\) 位,已有 \(j\) 组 \(a>b\) 的方案数,剩下的随意分配,即对于所有的 \(f[n][i]\) 都要乘上一个 \((n-i)!\)
我们想要的就是 \(a>b\) d的组数恰好为 \(\frac{n-k}{2}\) 的方案数
我们现在对 \(f[n][i]\) 中 \(i > \frac{n-k}{2}\) 的部分进行一个容斥,令 \(m=\frac{n-k}{2}\) ,那么就有
\[\text{ans}=\sum_{i=m}^n(-1)^{i-m}\binom{i}{i-m}f[n][i] \]时间复杂度 \(\mathcal O(n^2)\)
HDU 4336 Card Collector （容斥原理套路4 min-max容斥）
题目
有 \(n\) 张卡牌，每次拆开一包方便面有 \(p_i\) 的概率得到第 \(i\) 张卡牌，保证 \(p_1 + p_2 + \cdots + p_n \le 1\) , 所以方便面里可能存在没有牌的情况，求收集完 \(n\) 张卡牌，需要拆开的方便面包数的期望
题解
\(\text{min-max容斥}\) 常用于解决形如“全部出现的期望时间”问题，处理方法如下：
记 \(t_i\) 为第 \(i\) 个物品出现的时间, \(\min(S)\) 表示集合 \(S\) 中的物品至少一个出现的期望时间,\(\max(S)\) 表示集合 \(S\) 中的物品全部出现的期望时间
又因为单位时间内 \(S\) 中出现至少一个的概率为 \(p\),那么在 \(S\) 中出现至少一个的期望时间就是 \(\frac{1}{p}\)
所以,对于本题,
\[\min(S)=\frac{1}{\sum_{i\in S}p_i} \]我们套用 \(\text{min-max容斥}\) 的公式就可以过掉这道题了
时间复杂度 \(\mathcal O(2^n)\)
ARC101E Ribbons on Tree (容斥原理套路2)
题目
给定一个 \(n\) 个点的树,\(n\) 为偶数,点与点之间两两配对,配对点之间的边被覆盖,问有多少种配对方式,使得每一条边都有被覆盖
\(n\le 5000\)
题解
直接计算是 \(\mathcal O(n^3)\) 的,无法通过本题
所以考虑容斥,设 \(S\) 表示没有被覆盖的边的集合,将这些视作断掉的边,那么就有
\[\text{ans}=\sum_{S\subset E} (-1)^{|S|}f(S) \]其中 \(f(S)\) 表示不能覆盖到 \(S\) 中边的方案数,那么答案就是
\[\text{ans}=\sum_{S\subseteq E}(-1)^{|S|}f(S) \]设 \(g(n)\) 表示 \(n\) 个点任意配对的方案数,那么有 \(g(n)=n!!\) (双阶乘)
设 \(\text{dp}[u][x]\) 表示结点 \(u\) 所在联通块大小为 \(x\) 时的方案数,注意此时 \(u\) 所在的联通块并没有独立出来,没有算在联通块总数中
对于 \(x\ge 1\) 的情况,转移就是树上背包,复杂度证明与"BZOJ 4033 树上染色"是一样的
对于 \(\text{dp}[u][0]\) 的情况,此时我们就将当前点 \(u\) 所在的联通块独立出来,也就是钦定了 \(u\) 到其父亲的这条边被删掉了,我们有 \(\text{dp}[u][0]=-\sum_{x=1}^{\text{siz}_u}\text{dp}[u][x]\times g[x]\) 因为此时被删掉的边集大小大了 \(1\)
时间复杂度 \(\mathcal O(n^2)\)
BZOJ 4767 两双手 （容斥原理套路2）
题目
棋盘上 \((0,0)\) 处有一个棋子。棋子只有两种走法，分别对应向量 \((A_x,A_y),(B_x,B_y)\)。同时棋盘上有 \(n\) 个障碍点 \((x_i,y_i)\)，棋子在任何时刻都不能跳到障碍点。
求棋子从 \((0,0)\) 跳到 \((E_x,E_y)\) 的方案数。答案对 \(10^9+7\) 取模
\(E_x,E_y,n\le 5000\),保证 \((A_x,A_y)\) 与 \((B_x,B_y)\) 不共线
题解
因为两个向量不共线,由平面向量基本定理,加之旗子只有两种走法,我们可以找到对于一个变换后坐标为 \((x_1,y_1)\) 的点 \(A\) 和坐标为 \((x_2,y_2)\) 的点 \(B\),那么从前者走到后者的方案数就是 \(\binom{x_2-x_1+y_2-y_1}{x_2-x_1}\),记这个方案数为 \(\text{cnt}[A][B]\)
接着我们考虑容斥原理的套路 \(2\),设 \(f[i]\) 表示 \(i\)障碍之前不经过任何障碍到达障碍 \(i\) 的方案数,转移有
\[f[i]=\text{cnt}[i][0]-\sum_{j=1}^{i-1}f[j]\times \text{cnt[j][i]} \]时间复杂度是 \(\mathcal O(n^2)\)
ZR2022 NOIP十连测 Day5 T3 （数位dp+容斥原理套路1）
题目
小K想知道你可不可以帮他验算。
小K有 \(k\) 个在 \([0,x]\) 范围内的随机整数 \(a_1,\ldots,a_k\)，记 \(f(x)\) 表示 \(x\) 的所有非零数位的积，例如 \(f(0)=1,f(1145141919810)=1\times1\times4\times5\times1\times4\times 1\times9\times1\times9\times8\times1f(0)=1,f(1145141919810)=1\times1\times4\times5\times1\times4\times 1\times9\times1\times9\times8\times1\)。现在小 \(k\) 想知道 \(f(\sum_{i=1}^ka_i)\) 的期望值。
小K已经用超级计算机计算出了精确值，所以你只需要算出答案乘上 \((x+1)^k\) 对 \(10^9+7\) 取模的值帮他验算就好了
\(k\le 20,n\le 10^{10^{4}}\)
题解
毒瘤题!
乍一看就很像一个数位dp,但这道题困难的地方在于如何求出每一个 \(f(n)\) 它的系数是多少,并且如何将这个系数分离出来变成数位dp可做的东西
然后难的就是这一部分,所以我把这题归到了计数dp中(尽管它看着更像是一个数位dp)
我们设 \(g(n)\) 表示使得 \(\sum_{i=1}^ka_i=n\) 的方案数,那么考虑容斥,有
\[g(n)=\sum_{i=0}^k(-1)^i\binom{k}{i}\binom{n-(x+1)i+k-1}{k-1} \]组合意义就是对大于 \(x+1\) 的数的个数进行容斥,后面那一部分考虑整体加一后插板
于是我们要求的答案就变成了
\[\begin{aligned} &\sum_{i=0}^{kx}f(i)g(i)\\ =&\sum_{i=0}^{kx}f(i)\sum_{j=0}^{k}(-1)^j\binom{k}{j}\binom{i-(x+1)j+k-1}{k-1}\\ =&\sum_{j=0}^{k}(-1)^j\binom{k}{j}\sum_{i=0}^{kx}\binom{i-(x+1)j+k-1}{k-1}f(i)\\ =&\sum_{j=0}^{k}(-1)^j\binom{k}{j}\sum_{l=0}^{k-1}c_{j,l}\sum_{i=0}^{kx}f(i)i^l \end{aligned} \]其中
\[c_{j,l}=[i^l]\binom{i-(x+1)j+k-1}{k-1} \]这个东西显然是可以 \(\mathcal O(k^4)\) 暴力做的
这样我们的问题就转化为求
\[\sum_{i=0}^{kx}f(i)i^l \]我们参考以往数位dp的经验,对上面那个式子进行转移,设 \(\text{dp}[j]=\sum_{i=0}^{kx} f(i)i^j\) ,假设我们枚举当前位 \(\text{now}\) 的取值为 \(x\) ,加完上一位时得到的数位 \(\text{num}\) 那么有转移
\[\text{dp}[a+b] \leftarrow f(\text{num}+x\times 10^{\text{now}})\times (\text{num}+x\times 10^{\text{now}})^{a+b} \]即从
\[\begin{aligned} &f(\text{num}+x\times 10^{\text{now}})\times (\text{num}+x\times 10^{\text{now}})^{a+b}\\ =&\binom{a+b}{a}\times f(x)\times f(\text{num})\times \text{num}^b\times (x\times 10^{\text{now}}) ^a\\=&\binom{a+b}{a}\times f(x)\times \text{dp}[b]\times (x\times 10^{\text{now}}) ^a \end{aligned} \]转移而来
最后注意 \(\binom{n}{m},(n< m)\) 时是 \(0\) ,而我们在算系数的时候会把这玩意算负,所以最后那个式子改成
时间复杂度 \(\mathcal O(k^4+k^3\lg x)\)
[SRM 697] ConnectedStates （prufer序列计数）
题目
有\(n\)个城市，每个城市有个权值\(w_i\)，任意两个城市\(i,j\)之间的道路数有\(w_i\times w_j\)条。对于每种生成树，若每个点的度数为\(d_i\),则贡献为 \(\prod d_i\)。求所有无根生成树的权值和。
\(n\le 1000\)
题解
吐槽：真毒瘤
这是一个有标号无根树问题，所以我们可以考虑搞出它的\(\text{prufer}\)序列，每个点的个数就是\(\text{prufer}\)序列中出现的次数\(+1\)
对于一个固定的\(\text{prufer}\)序列(无根树)，方案总数显然是\(\prod w_i^{d_i}\)
贡献就再乘上度数之积为\(\prod d_iw_i^{d_i}\)
然后我们再算有多少种\(\text{prufer}\)序列，每个数都有一个出现次数的全排列显然是多重组合数，所以方案数有
\[\frac{(n-2)!}{\prod(d_i-1)!} \]因此我们最终所要求的东西就是
\[\sum_{\sum d_i=2n-2}\frac{(n-2)!}{\prod(d_i-1)!}\prod d_iw_i^{d_i}\\=(n-2)!\sum_{\sum d_i=2n-2}\frac{\prod d_iw_i^{d_i}}{\prod(d_i-1)!} \]设\(f[i][j]\)表示考虑到第\(i\)个数，度数和为\(j\)的方案数，枚举当前位的度数\(k\)，转移就乘上一个\(\frac{kw_i^{k}}{(k-1)!}\),这部分可以预处理出来
所以暴力转移的复杂度是\(\mathcal O(n^3)\)的
考虑使用多项式的幂公式，即
\[(x_1+\cdots+x_t)^n=\sum_{\sum t_i=n}\binom{n}{t_1,t_2,\cdots t_n}\prod x_i^{t_i} \]我们令\(a_i=d_i-1\),那么有
\[\begin{aligned} \text{原式}&=(n-2)!\sum_{\sum a_i=n-2}\binom{0}{a_1,a_2,\cdots,a_n}\prod (a_i+1)!w_i^{a_i+1}\\&=(n-2)!\prod w_i\sum_{\sum a_i=n-2}\binom{0}{a_1,a_2,\cdots,a_n}\prod (a_i+1)!w_i^{a_i} \end{aligned} \]现在我们离化简只差\(\prod (a_i+1)\)这个东西了，考虑它实际上是在枚举子集(枚举\(a_1\sim a_n\)几个相互组成的单项式)，我们考虑当前我们枚举到的单项式是\(a_2a_3a_7\),那么这个单项式对答案的贡献为(注意单项式被乘进了分母里,所以对应的加和也要减\(3\)),前面\((n-2)!\prod w_i\)就先不管了
\[w_2w_3w_7\frac{1}{(n-5)!}\sum_{\sum a_i=n-5}\binom{n-5}{a_1,a_2-1,a_3-1,\cdots,a_n}w_i^{a_i}\\=w_2w_3w_7\frac{1}{(n-5)!}(w_1+\cdots+w_n)^{n-5} \]所以类比到整个式子就变成了
\[(n-2)!\prod w_i \sum_{k=0}^{n-2}(\sum_{从n-2个里面选k个}\prod w_i)\frac{(w_1+\cdots w_k)^{n-2-k}}{(n-2-k)!} \]\(f[t][k]\) 表示只考虑使用前 \(t\) 个数组合，所有 \(k\) 项式之和是多少。
转移就是 \(f[t][k]=f[t−1][k]+f[t−1][k−1]\times w_t\)
那么这道题就可以 \(\mathcal O(n^2)\)