数数
数数题
会把计数相关问题放在这里.
一做数数发现现在已经不会做蓝题了.
1. Appleblue17
这一部分是appleblue17的cf和其他数数选做里的前几个.
CF1515E Phoenix and Computers
有 $n$ 台电脑排成一排, 每次可以手动打开一台没被打开的, 同时若一台电脑左右的电脑都被打开, 那么它会自动打开. 求把所有电脑打开的方案数. $n\le 400$
发现自动打开的电脑两边一定是手动打开的, 即它们不可能相邻, 所以其实是若干段手动打开的, 段段之间夹着一个自动打开的.
手动打开一个连续区间的方案数是 $2^{len-1}$ , 原因是我们每次只能像左边和右边拓展, 那么设第一个打开的是第 $k$ 个, 方案就是在剩下 $len-1$ 步中选 $k-1$ 步是向左拓展的, 所以方案数是
$$
\sum_{k=1}^{len} \binom{len-1}{k-1}=2^{n-1}
$$
那么把一个自动打开的和紧跟着的一段手动打开的作为一段, 设 $f_i$ 表示前 $i$ 个的方案, 则加上一个新段的方案数时除了乘上这一段的方案, 还要再在总步数里选若干步是新的这段的方案, 那么我们要知道总步数, 所以还要记录总步数或者之前分了几段, 增加一维, 设 $f_{i, j}$ 表示前 $i$ 个分了 $j$ 段, 转移就是
$$
f_{i, j}=f_{k-1, j-1}\times \binom {i-j+1}{i-k}\times 2^{i-k+1}\
f_{-1, 0}=1
$$
要把0当成一个自动开启的电脑留出来, 所以边界就成了-1, 实际实现可以所有下标一起加一
P6944/LOJ3405 [ICPC2018 WF]Gem Island
有 $n$ 个人每个人有一个宝石, 每天会随机一个宝石分裂成两个, 求 $d$ 天后拥有宝石前 $r$ 多的人所拥有的宝石数之和的期望, 不膜. $n, d\le 500$
设序列 $A$ , $a_i$ 表示 $d$ 天后第 $i$ 个人拥有的宝石数, 试着算算它出现的概率.
$$
\begin{aligned}
\text{A的方案数}&=\dfrac {d! }{\prod_i (a_i-1)! }\times \prod(a_i-1)! \
&=d!
\end{aligned}
$$
解释一下这个式子:
乘号左边的部分是我们确定下来每一天是给哪个人加的, 这个过程相当于对于一个天数构成的排列对一个排列我们让前 $1-a_1$ 个给第一个人, 接下来 $a_2$ 个给第二个人. . . 再除掉这么每一组分组后组内相对顺序.
乘号右边的部分是把每天由谁得这个关于人的方案数再变成关于宝石的方案数, 考虑一个人第 $i$ 次收获宝石的方案数是 $i-1$ , 那么这个人 $i$ 得到宝石的方案数就是 $(a_i-1)!$ 再乘起来.
于是发现每个 $A$ 的概率是相同的, 那么接下来就是算对于所有的 $A$ 它们的前 $r$ 大之和, 先考虑如何求 $A$ 的方案数, 此时可以先减去每个人一开始有的那个宝石方便计算:
这时有一种十分奇妙的状态设计, 考虑由于我们不关心 $a_i$ 的顺序, 所以我们假定它是递减的, 我们把宝石排成一个矩阵, 第 $i$ 列表示第 $i$ 个人的情况, 像这个样:
1 | **** |
这个图对应的 $A$ 是 $6, 6, 6, 6, 5, 5, 4, 4, 4, 2, 2$
横着关于人递推是困难的, 于是把它竖着递推, 由于此时向上递推时更高的顶大小一定小于更低的所以我们要知道顶的大小, 由于最后要求 $\sum a_i=d$ 所以要记录和, 于是设 $f_{i, j}$ 表示一共有 $j$ 个宝石, 其中有顶有 $i$ 个的方案数, 那么转移就是枚举上一层的大小, 即
$$
\begin{aligned}
f_{i, j}&=\sum f_{k, j-i}\times\binom{k}{i}\
f_{n, 0}&=1
\end{aligned}
$$
可以类比这个列出和的, 设顶大小为 $i$ , 共 $j$ 个的所有情况前 $r$ 大和的和为 $g_{i, j}$ , 则有转移:
$$
\begin{aligned}
g_{i, j}&=\sum (g_{k, j-k}+f_{k, j-k}*min(r, i))*\binom{k}{i}\
g_{n, 0}&=0
\end{aligned}
$$
然后dp就行了, 这个题不膜, 要直接带着long double从头算到尾.
CF1630E Expected Components
收录到[polya定理初学](https: //fireinicecode. github. io/2022/07/01/polya/)中
ARC132E Paw
给定字符串 $s$ 包含 $\texttt{< > . }$ 三种, 表示向左的足迹, 向右的足迹和洞. 你每次会随机一个洞钻出来, 把洞填平, 然后随机左右两个方向走到下一个洞或走出字符串, 并把沿途所有位置都覆盖为你走的方向的足迹(沿途不包括你停止的那个洞). 直到没有洞. 求最后局面向左足迹的期望个数.
$\vert s\vert \le 10^5$
这种题要考虑形成局面的性质.
发现我们最后的局面一定是 $\texttt{<<\ldots<<. ==\ldots==. >>\ldots>>}$ , 且 $\texttt{=}$ 两边两个洞中间没有洞, 这里 $=$ 表示未走过的地方. 因为考虑不会出现 $\texttt{>><<}$ 的情况是因为停止需要一个洞, 而由这个洞出发的时候要么覆盖顺延右边的 $\texttt{<}$ 的要么顺延左边的, 一定会把这个局面填掉. 不会出现 $\texttt{<<>>}$ 因为这个点在出发一个之后就没了不能出发一个相反的, 所以局面只能是相邻两个洞向外发出的足迹.
那么枚举相邻两个洞, 考虑形成这个局面的概率, 发现左右是独立的, 以向右部分为例, 若 $f_i$ 表示向右形成前 $i$ 个的全局概率(所有方案中右边是对的的概率), 则有 $f_i=f_{i-1}\times (1-\dfrac{1}{2n})$ , 意思是只有选到 $i$ 这个位置并且向左走不行. 发现直接把左右两边对应概率乘起来即可因为两边都是全局的概率且互不影响.
CF1621G Weighted Increasing Subsequences
给定 $a_n$ , 对于 $a$ 的所有上升子序列 $a_{i_1}\ldots a_{i_k}$ , 其权值为 $a_{i_j}<a_x\And x>k$ 的 $j$ 个数, 对所有上升子序列求和.
$n\le 2\times 10^5$
钦定每个上升子序列 $a_{i_1}\ldots a_{i_k}$ 被最后一个大于a_{i_k}的 $x$ 贡献.
于是枚举 $x$ , 考虑计算贡献.
那么 $a_x$ 与 $a_j$ 行成的贡献是在 $[1, x)$ 中的上升子序列个数(这里是于拆贡献成 $x$ 与上升子序列中每一个小于它的数对的个数).
这个就是以 $i$ 结尾的, 乘上以 $i$ 开头但没有接到 $x$ 的个数. 因为 $x$ 是最后一个大于 $a_k$ 的, 所以没有接到 $x$ 后面的子序列, 于是后面这个等于以 $i$ 开头的个数减去以 $i$ 开头, $x$ 结尾的个数.
考虑直接把这些数都拿出来跑一遍dp, 那么这两个都可以1log算. 注意到设 $y$ 为大于 $x$ 的最大的 $y$ , 则 $a_x\in [a_y, a_z)$ , 并且 $y$ 恰好是下一个 $x$ ( $x$ 就是后缀 $\max$ , $y$ 恰好是下一个后缀 $\max$ ), 所以每个 $x$ 只会被拿出来算一遍. 就结束了.
[think] 钦点的东西可能也需要枚举, 第一个, 最后一个, 最大的这样的.
2. luogu某题单
然后做不动了appleblue太强悍. 随便找点, 下面是luogu上的一个题单
CF1657E Star Mst
求 $n$ 个点的无向完全图有多少个满足最小生成树的权值和等于所有和点1相连的边的权值和, 每条边边权为 $[1, v]$ , $n, v \le 250$
qyc场切
这个条件首先等价于以1为根的菊花是它的最小生成树, 再考虑Kruskal的过程, 又等价于对于每个点, 1都是离它最近的点之一.
考虑对于一条 $u\to v, u, v\ne 1$ 的边, 在我们不知道 $1\to u$ 和 $1\to v$ 前是无法确定的, 所以要明确一个确定边权的顺序, 发现如果从小到大确定边权那么所有新的满足 $1\to u, 1\to v$ 已经确定的 $u\to v$ 的边权都只依赖于我们新加的边权而不依赖于旧的, 根据这个, 设 $f_{i, j}$ 表示加入了边权在 $[1, i]$ 的边, 一共有 $j$ 个连到 $1$ 上, 当转移时, 我们考虑新加入的这些边确定了哪些:
$$
f_{i, j}=f_{i-1, k}\times (v-i+1)^{\binom{j}{2}-\binom{k}{2}}\times \binom{j}{k}
$$
推转移式子的时候别忘了最后那个组合数.
注意指数上那个二项式系数不是对 $P$ 取模, 但其实也没事因为它们根本到不了要取模的大小.
然后你就做完了.
P5664 [CSP-S2019] Emiya 家今天的饭
给一个 $n$ 行 $m$ 列的矩阵 $A$ , 每个格子有个数表示选这个格子的方案数, 可以选任意多个格子, 要求每行只能选一个, 且若一共选了 $k$ 个数, 则不能有一列选超过 $\lfloor\dfrac{k}{2}\rfloor$ 个数. $n \le 100, m\le 1000$
这题首先看起来很dp, 发现这个每列个数不超过一半很难计算, 而又因为只可能有一列选的个数超过一半, 所以可以容斥, 枚举是哪一列超过了一半.
于是现在钦定第 $r$ 列超过一半计算方案数, 很容易想到设 $f_{i, j, k}$ 表示考虑这一列的前 $i$ 个数, 选了 $j$ 个第 $r$ 列的和其他 $k$ 个不在第 $r$ 列的. 这里记 $s_i=\sum_j A_{i, j}$ , 则转移为:
$$
f_{i, j, k}=f_{i-1, j-1, k}\times a_{r, i}+f_{i-1, j, k-1}\times (s_i-a_{r, i})
$$
但这样做算上枚举每一列的话复杂度是 $O(mn^3)$ 的, 无法通过, 发现我们之所以记录 $j$ 和 $k$ 是因为判断最后是否要这个值, 即是否在这一列里选了超过一半, 那么其实我们只要知道 $j-k$ 就行, 所以考虑设 $f_{i, j}$ 表示考虑这一列的前 $i$ 个数, 在这一列的比外面的多 $j$ 的方案数, 发现转移是简单的, 复杂度就成了 $O(mn^2)$
启发一种优化状态设计的方法.
P3214 [HNOI2011] 卡农
有 $m$ 个音, 要求选出无序的 $n$ 个互不相同的音的集合, 满足所有音都出现了偶数次. 对 $10^8+7$ 取模.
$n, m\le 10^6$
首先 $10^8+7$ 居然也是质数, 长见识.
首先这个的无序没有任何用处, 有序的除以 $n!$ 就行.
由于是偶数次, 让人想到异或, 所以转化为:
在 $[1, 2^m -1]$ 个数中选 $n$ 个互不相同的数满足异或和为0.
设选前 $i$ 个数的答案为 $f_i$ , 如果我们先随便放 $[1, i-1]$ , 最后在 $i$ 的位置放一个数 $x=a_1\operatorname{xor}a2. . . \operatorname{xor}a_{i-1}$ 就满足了条件, 这样的方案数是 $A^{i-1}_{2^m-1}$ 但却多算了以下两种情况:
$x=0$ , 说明前 $i-1$ 个已经异或起来是0了, 多算了 $f_{i-1}$ 个方案.
$x$ 在前面出现过, 那么把那个出现过的也删去, 剩下的还有 $f_{i-2}$ 个方案, 此时 $x$ 有 $2^m-1 -(i-2)$ 种可能(与前面的其他数互不相同), 同时与其相同的那个数的下标有 $i-1$ 种, 一共多算了 $(2^m-1-(i-2))(i-1)f_{i-2}$ 个方案.
最后注意
$$
A^k_n\bmod P=A^k_{n\bmod P} \bmod P
$$
可以简单归纳法证明.
P2606 [ZJOI2010]排列计数
求有多少个长为 $n$ 的排列满足 $p_{i}>p_{\frac{i}{2}}$ . $n \le 10^6$
容易想到若 $i$ 向 $\dfrac{i}{2}$ 连边会得到一棵完全二叉树, 而此时根一定是当前最小值, 左右子树则是互不干扰的, 形成一个递归结构, 于是我们考虑dp.
设 $f_i$ 表示长度为 $i$ 的排列的答案, 也就是节点数为 $i$ 的树的答案, 同时设 $lson_i, rson_i$ 表示它左右子树的大小, 则有:
$$
f_{i}=\binom i {lson_i}\times f_{lson_i}\times f_{rson_i}
$$
然后做完了.
P6453 SP3734 PERIODNI - Periodni
给定一个 $n$ 列直方图(底部对齐的若干矩形)网格, 每列高度各不相同, 现在要在其中摆放 $k$ 个车, 要求车相互无法攻击. 求摆放方案数.
$n, k\le 500$ .
看到这个直方图想到给定直方图求最大矩形那个题的笛卡尔树做法, 我们把笛卡尔树建出来dp, 考虑以序列下标为二叉查找树的关键字, 以矩形高度建小根笛卡尔树, 因为每一列高度各不相同所以, 所以相当于把直方图横向分隔成若干层, 如图:
那么接下来只要考虑如何在这棵树上dp, 容易想到设 $f_{u, i}$ 表示 $u$ 的子树内放了 $i$ 个车的方案数, 若 $v$ 为 $u$ 的儿子, 发现仅仅在自己这里选择 $j$ 个的方案数就是 $\binom{w}{j}\binom{h}{j}j!$ , 然后按这个转移即可.
P3244 [HNOI2015]落忆枫音
给定 $n$ 个点 $m$ 条边的DAG, 在此基础上再添加一条 $x\to y$ 的边, 求此时以1为根的不同的生成树个数. $n\le 10^5$
在DAG上这个东西时好求的, 只要把每个点的入度乘起来即可, 意思是给每个点选一个父亲. 但现在又多了一条边, 可能形成至多一个环, 那么只要减去恰好选了这个环的方案, 相当于我们只确定了环上点的父亲, 所以方案数就是不在环上的所有点的入度的乘积, 两者相减即可.
P6672 [清华集训2016] 你的生命已如风中残烛
$m$ 张牌的牌堆, 牌是区分的, 同时 $n$ 张牌还有属性 $w$ 表示可以打出后能再摸几张, 求有多少种牌堆的排列使得你一轮可以把所有牌都摸没. 保证 $\sum w=m$ .
首先可以把没有属性 $w$ 的牌看成 $w=0$ .
考虑摸没的条件, 摸完前 $k$ 张牌的手牌数为 $1+\sum_{i=1}^k w_i - k$ , 所以要求对于任意 $k$ 这个式子为正, 于是可以给每个 $w_i$ 先减去1. 变成保证 $\sum_i w_i=0$ , 要求所有前缀和都非负的个数.
有一个Raney引理: 对任意和为1的整数排列, 其所有循环平移形成的排列中, 有且仅有一个满足任意前缀和为正.
这个证明很简单, 看成折线图后就是只有从折线图的最低点出发的情况满足条件. 如果有多个相同的最低点则只能选最后一个, 所以只有一个出发点满足条件.
但这个问题没有和圆排列的直接一一对应的关系, 原因是当出现多个最低点时可以选择任意一个.
可能会想到在开头处添加一个1转化过去, 会发现我们在原始问题上添加1可能导致去掉这个1后两种方案本质相同. 因为第一个位置的数不一定是1.
但如果在最后添加一个-1就没有问题, 因为假设仍有多个最低点只能选第一个, 否则我们会跨过这个-1来到第一个最低点, 那么第一个最低点的位置就会比当前的更低. 于是我们又建立起了一一对应的关系.
接下来计算答案就简单了. 要注意这里 $w$ 相等的卡牌是区分的, 所以不用Polya而可以直接圆排列计数, $m+1$ 个卡牌的圆排列一共有 $\dfrac{(m+1)! }{m+1}=m!$ 个, 同时由于我们添加的-1和其他-1是不区分的, 所以除掉-1个数 $m-n+1$ , 答案为 $\dfrac{m! }{m-n+1}$ .
3. CF板刷
CF选择标签combination板刷
CF1730E Maximums and Minimums
给定序列 $a$ , 求区间中最大值是最小值的倍数的区间个数.
$n\le 5\times 10^5, a_i\le 10^6$
$10^6$ 以内因数个数不到300. 于是算法复杂度有可能是 $nd$ 的. (不然应该出到 $10^9$ )吧.
枚举最大值和对应因数, 我们能做到 $nd\log n$ . 这个部分还很套路: 就是考虑能做最大值的区间, 对应最小值能做最小值的区间. . . $\log n$ 出现在对于每一个最大值找出左边/右边第一个最小值的位置.
但是问题是, 怎么去 $\log n$ 呢? 好, 打开jiangly代码, lower_bound, 嗯, 结束了. 原来是 $nd\log n$ .
哦去 $\log$ 是简单的, 考虑我们相当于 $nd$ 次询问一个数左边等于另一个数的位置. 那么假设最大值枚举的时候从左往右, 就只需要对于每一个值维护它最后一次的位置即可.
另一个做法是分治, 但是我不会啊.
CF1728G Illumination
给定一条长 $d$ 数轴上的 $n$ 个灯和 $m$ 个点的位置序列 $l, p$ , 灯 $i$ 可以照亮 $[l_i-w_i, l_i+w_i]$ 范围内的点, 其中 $w_i$ 是 $[0, d]$ 的整数.
$q$ 次询问, 每次询问在已有 $n$ 个灯的基础上添加一个新灯后 $w$ 的方案数使得每一个点都能被照亮.
$n\le 2\times 10^5, m\le 16, q\le 5\times 10^5, d\le 3\times 10^5$ .
先考虑一次询问怎么做, 能dp吗?
$f_{i, j}$ 表示前 $i$ 个灯照亮前 $j$ 个点, 发现可以转移. 那么直接转移写成矩阵, 预处理前缀积和后缀积就行了. 复杂度是 $nm^3+qm^3$
另一个做法是考虑容斥, 枚举点集 $S$ , 确定它们都被覆盖是困难的, 但要求 $S$ 内的点都不被覆盖只要让相邻两个属于 $S$ 的点之间的灯照不到这两个端点即可. 相当于直接限制每个灯的最大值. 那么预处理数组 $f_{l, r}$ 表示 $[l, r]$ 中的灯照不到点 $l$ 和 $r$ 即可.
现在有了多组询问, 枚举新加的点照亮的范围, 并预处理照亮这个范围外的点的方案. 注意范围外的点这一点集一定是前缀和后缀, 所以点集只有 $m^2$ 个.
CF1671F Permutation Counting
求逆序对数为 $k$ , 下降数为 $x$ 的长 $n$ 的排列数量.
$n\le 998244352, k, x\le 11$
下降数是 $\sum [a_i>a_{i+1}]$
牛逼题.
把满足 $i<\max_{j\le i} a_j$ 的连续的一段称为一段, 那么发现段间没有贡献.
[think] 拆贡献的思想
对于每一段, 考虑其内部排列, 一段长度最多是 $12$ 否则逆序对数就会超过 $11$ , 于是就先考虑内部排列, 设 $f_{s, j, k}$ 表示 $s$ 集合已经选了, 有 $j$ 个逆序对, $k$ 个下降的一段的个数, 枚举下一个填几即可转移. 就能 $2^12\times 11^2\times 12$ 的dp它了.
接下来考虑, 一个长度是 $2$ 的段会产生 $1$ 个逆序对, 所以我们最多拼 $11$ 个段, 于是设 $g_{i, j, k, l}$ 表示拼了 $i$ 个段, 这 $i$ 个段一共 $j$ 个数, 有 $k$ 个逆序对, $l$ 个下降的方案数, 转移是类似背包的dp.
最后算答案的时候, 我们累加所有 $k, l$ 是题目要求的那些状态值, 那么对于除了这些长为 $2$ 的段之外的那些长为1的段, 每一个数都是唯一确定的, 于是直接用隔板法再乘一个组合数即可.
很厉害啊
更好想的感觉是另一个: 猜测固定 $i, j$ 后答案是关于 $n$ 的, 次数不超过 $11$ 的多项式, dp打出 $11\times 11\times 11$ 的表, 然后拉格朗日差值.
CF383E Vowels
给出 $n$ 个长度为 $3$ 的由 $\texttt{a}\ldots\texttt{z}$ 组成的单词, 一个单词是正确的当且仅当其包含至少一个元音字母. 这里的元音字母是 $\texttt{a}\ldots\texttt{x}$ 的一个子集. 对于所有元音字母集合, 求这 $n$ 个单词中正确单词的数量平方的异或和.
$n\le 10^4$
一个单词是错误的当且仅当这个单词与元音字母集合不交, 等价于它的补集是元音字母集合超集, 于是补集之后做超集和就能得到数量.
但问题是这样是 $10^7$ 的, 且没有利用单词长度为3的特性.
看题解, “注意到4s, 所以 $O({\vert\sigma\vert}2^{\vert\sigma\vert})$ 完全能过. “这样啊.
CF1603F October 18, 2017
给出 $n, k, x$ , 求长 $n$ , 每一项在 $[0, 2^k)$ , 且任意子序列异或和不为 $x$ 的序列个数. $n\le 10^9, k\le 10^7, \sum k\le 5\times 10^7, x< 2^20$
$x=0$ 是特殊的, 其他是相同的.
当 $x=0$ 时, 相当于选出若干个线性无关向量. 方案数为 $\prod 2^k-2^{i}$ , 就是每一次选前面不能表示的. 复杂度 $O(k)$
当 $x\ne 0$ 时, 每个数的情况相同, 所以求对于一个序列其能表示的数的个数求和后再除以数的总数就是答案. 而一个数列能表示的数的个数就是, 若把这个数列中所有数视作向量弄成一个矩阵后矩阵的秩为 $r$ , 个数就是 $2^r$ . 于是只要求长 $n$ 的序列秩为 $1\ldots n$ 的分别是多少即可.
考虑dp这个东西, 设 $f_{i, r}$ 表示前 $i$ 行, 秩为 $r$ 的方案数. 有
$$
f_{i, r}=f_{i-1, r}\times 2^{r}+f_{i-1, r-1}\times (2^k-2^{r-1})
$$
复杂度 $nk$
用生成函数求, 写成生成函数, 我们可以先选出一组基, 方案数是 $\prod_i (2^k-2^i)$ , 然后再把其他的数添加进去, 第 $i$ 个数后添加方案数是 $2^i$ . 后面这个生成函数是
$$
\prod \dfrac{1}{1-2^ix}
$$
而
$$
\dfrac{1}{\prod ^n_{i=0}\times (1-q^ix)}=\sum_{i>=0}x^i{i+n\brack n}_q
$$
所以后面这个生成函数 $n-r$ 项系数就是 ${n\brack n-r}_q$
于是就做完了.
生成函数=不可做
CF1295F Good Contest
求长 $n$ 序列 $a$ 单调不增的概率, 其中 $a_i$ 在 $[l_i, r_i]$ 中等概率随机.
$n\le 50, l_i, r_i\le 998244353$
$f_{i, j}$ 表示前 $i$ 个单调不增以 $j$ 结尾的方案数, 则
$$
f_{i, j}=(\sum_{k\ge j} f_{i-1, k})
$$
但值域很大, 会寄.
$f_i$ 是 $f_{i-1}$ 做后缀和再截取一个区间, 有什么好办法?
离散化成若干值域区间! 变成 $a_i$ 在第 $j$ 个值域区间, 那么此时转移要考虑一个区间内转移到当前区间内的情况, 发现根本不会做.
考虑不枚举 $j$ 转而枚举 $i$ , 即从 $f_{k}{j-1}$ 转移过来, 这样只要算从最后一段里选一个不降的序列即可. 而从长 $l$ 的值域段选长 $a$ 的不降序列只要组合数 $\binom {l+a-1}{a-1}$ 即可.
CF1523E Crypto Lights
有 $n$ 个台灯初始时都是暗的, 每次等概率随机一个暗台灯将其点亮, 若点亮后存在一个长度为 $k$ 的连续段有大于一个台灯被点亮则立刻停止, 求期望点亮多少台灯. 答案对 $10^9+7$ 取模.
$n, k\le 12^5$
考虑算开启 $i$ 个后能继续的概率.
那么这个就是从这 $n$ 个灯中选 $i$ 个灯相隔 $k$ 以上的概率. 这个考虑选 $i$ 个相隔 $k$ 以上的灯可以看作选 $i$ 个灯亮, 再在其中插入剩下的灯. 那么方案数就是 $\binom {n-i+(i-1)(k-1)+i}{i}\times i!$ . 就结束了.
CF1495D BFS Trees
给定一张图, 以 $s$ 为根的生成树是厉害的指 $s$ 到任意一点的树上距离等于实际距离. 求有多少个生成树同时是以 $x$ 为根厉害的也是以 $y$ 为根厉害的. 对所有 $(x, y)$ 求答案.
$n\le 400, m\le 600$
考虑如果 $x\to y$ 有两条及以上最短路, 那么一定不行.
找到这一条后, 这一条链一定原封不动照搬到这棵树上. 对于剩下的点, $u$ 的父亲可以为 $f$ 当且仅当 $dis(u, x)=dis(x, f)+1, dis(u, y)=dis(y, f)+1$ .
然后统计每个点可以的父亲个数, 直接乘起来就结束了.
CF1264D Beautiful Bracket Sequence
给定一个含 $\texttt{? }$ 的括号序列. 定义一个括号序列的权值为删除一些字符使其成为合法的匹配括号串后, 括号匹配的最深深度. 求把 $\texttt{? }$ 替换成括号的所有方案中, 括号序列的权值之和.
Version1
$n\le 2000$
注意不要求替换之后的合法.
我们枚举深度最大的匹配之间的空隙(如果有多个, 算在第一个空隙). 设左边有 $l$ 个左括号, 右边有 $r$ 个右括号, 左边有 $x$ 个问号, 右边有 $y$ 个. 那么方案数就是
$$
\sum_{i=0}^{x} (l+i)\times \binom xi \binom {y}{l+i-r}
$$
含义是枚举左边有多少个问号是左括号, 那么 $l+i$ 是深度, $\binom xi$ 是从左边挑出 $x$ 个, $l+i-r$ 是右边需要这么多括号定为右括号. 是我们钦定它是第一个深度最大的空隙并且右边确定了对应数量的右括号, 所以左边所有左括号都是可以贡献给这个空隙的. 所以这是正确的. 复杂度 $O(n^2)$
Version2
$n\le 10^6$
考虑化简这个式子:
$$
\begin{aligned}
& \sum_{i=0}^{x} (l+i)\times \binom xi \binom {y}{l+i-r}\
=& l\sum_{i=0}^{x} \binom xi \binom {y}{l+i-r} +
\sum_{i=0}^{x} i\binom xi \binom {y}{l+i-r}\
=& l\sum_{i=0}^{x} \binom xi \binom {y}{l+i-r} +
x\sum_{i=0}^{x} \binom {x-1}{i-1} \binom {y}{l+i-r}\
=& l\sum_{i=0}^{x} \binom {x}{x-i}\binom {y}{l+i-r}+x\sum_{i=0}^{x} \binom{x-1}{x-i}\binom {y}{l+i-r}\
=&l\binom{x+y}{x+l-r}+x\binom{x+y-1}{x+l-r}
\end{aligned}
$$
拿这个做即可.
第二部分知道范德蒙德卷积应该是简单的. 主要是第一部分枚举一个关键(最大值)的位置后计算组合数这个方法比较巧妙.
CF1437F Emotional Fishermen
给定长 $n$ 的序列 $a$ , 求 $a$ 重新排列后, 对于每一个位置 $a_i$ 和 $x=\min_{j\in[1, i-1]} a_j$ , 满足 $x\ge 2a_i$ 或 $a_i\ge 2x$
膜998244353. $n\le 5000$
考虑用 $a_i\ge 2x$ 的把序列分成若干段, 每一个段的划分点都是 $2a_i\le x$ , 每一个数可以作为划分点, 或放在第一个大于自己二倍的划分点之后. 排序后用这个dp. 设 $f_i$ 表示最大值是 $a_i$ 的方案数(加入小于 $\dfrac{a_i}{2}$ 的所有数), 此时排列中被加入的数目设为 $len_i$ .
$$
f_i=\sum f_j \times A^{len_i-len_j-1}_{n-len_j-2}
$$
$f_i$ 位置是 $a_j$ 后第一个没被放的位置(否则空出来一个位置没有东西可以放), 它的位置是确定的. 而在值域 $(\dfrac{a_j}{2}, \dfrac{a_i}{2}]$ 中的这些数可以再这一次被加入. 并且可以在自己后面任意放(不能在前面, 前面已经没空位了). 于是就是这个样子了. 复杂度 $n^2$ .
仍然是费用提前计算的思想(不过把费用改成方案数). 我们应该有意识枚举所有可能都状态设法和转移方向. 并且dp排列的时候由于其每个值只能出现一次基本都是从值域入手把值域分成若干段去计算.
CF1237F Balanced Domino Placements
给定一个 $n\times m$ 的棋盘, 上面放了 $k$ 个 $1\times 2$ 的骨牌, 要再任意放骨牌, 要求同一行, 同一列只有最多有一个骨牌, 求方案数.
$n, m\le 3600, k\le 2400$
行和列是隐晦的独立的.
看起来似乎行和列会互相影响. 但实际上可以看作, 若选择 $x$ 个横放和 $y$ 个竖放, 就是要选择 $x+2y$ 行, 其中有 $y$ 对两两相邻. 对列也一样. 那么确定这个选择的方案之后剩下就是两两配对了. 所以预处理 $f_{x, y}, g_{x, y}$ 分别表示在确定横竖个数之后选行列的方案数, 答案就是
$$
\sum f_{x, y}g_{x, y}x! y!
$$
注意这里不是 $(x+y)!$ , 因为 $2y$ 个相邻行和只能和 $y$ 列匹配, $2x$ 个相邻列和 $x$ 行匹配, 两组匹配是独立的.
最后就是处理 $f, g$ 的问题了. 以 $f$ 为例, 对于每一个能选的行当连续段且确定 $x, y$ 后方案数很好确定. 那么这么背包上去只能做到三次方.
我们不需要同时考虑 $x$ 和 $y$ , 可以先确定选 $y$ 个行对当方案数, 再在剩下的里面选单独行是直接组合数. 而第一个就dp就好了. 前 $i$ 行选 $j$ 对的方案这样的. 就做完了.
dwt钦定是简单题///ll
! dwt
CF1185G Playlist for Polycarp
有 $n$ 首歌, 每一首长 $t_i$ , 类型为 $g_i$ , 求选择一些歌并排列的方案使得任意两个相邻 $g_i$ 不同且总时长恰好为 $T$ .
$g_i\le 3$
Version1
$n\le 15, T\le 225, t_i\le 15$
直接状压dp. $f_{s, i}$ 表示 $s$ 已经被选了, 最后一个选的第 $i$ 首.
Version2
$n\le 50, T\le 2500, t_i\le 50$
不能直接状压dp了, 需要组合数学靠运气.
我们可以直接处理满足编号限制的dp: $f_{i, j, k, 0/1/2}$ 表示 $i$ 个第一种, $j$ 个第二种, $k$ 个第三种, 最后一个是哪一种的方案数. 暴力转移.
那么接下来就要考虑一个合法集合使得满足时间限制. 看看数据很小可以直接枚举 $i, j, k$ , 那么就要知道此时等于时间的方案数. 这是一个subset sum, 不过有三个集合. 所以就使劲背包就好了.
CF1558D Top-Notch Insertions
对于一个长度为 $n$ 的序列 $a$ 做插入排序, 即依次考虑 $a_2, \cdots, a_n$ 每个元素:
如果 $a_i \ge a_{i - 1}$ , 即前缀依然保持不下降, 不做操作.
否则, 找到最靠前的位置 $p$ , 使得 $a_i < a_p$ , 然后将 $a_i$ 插入到 $a_p$ 前面, 并重新标号序列. 记这次插入为 $(i, p)$ .
接下来给定 $m$ 个二元组 $(x_i, y_i)$ , 求有多少个长度为 $n$ 的序列 $a$ , 满足 $\forall i, a_i \in [1, n] \cap \mathbb N$ 且做插入排序恰好按照给出的元组进行给定的 $m$ 次插入.
输出序列的数量对 $998244353$ 取模的结果.
根据若干个插入条件, 可以唯一确定原序列相对顺序. (就是这些插入相当于对原序列做了一个置换重排, 根据这个可以获得 $a$ 的排序.
但此时拿到的 $a$ 并不是一个不降的要求(我们会得到若干 $>$ 和若干 $\ge$ 串起来的关系), (可以理解一下这个关系蕴含了能获得的全部信息), 我们需要知道其中有几个是大于几个是大于等于. 一个数前面是小于当且仅当是另一个数直接插入到自己前面, 于是用平衡树维护序列即可.
平衡树不断插入有些麻烦, 反过来变成删除即可.
CF1536F Omkar and Akmar
两个人在一个长度为 $n$ 的环上放黑白棋, 每个人在一个空格子里放一个颜色不能与相邻棋子相同的棋子, 问如果两人都采用最优策略, 可能的游戏过程有多少种.
$n\le 10^6$
手玩几组发现后手好像总会赢.
结论是: 后手只要走, 无论怎么走都赢. 因为最后一定是若干个黑白交替连续段中间夹着单个空格, 且空格两边颜色一定不同. 所以总棋子数一定是偶数. 所以这俩人实际上是随便走, 然后后手能赢.
于是就可以直接计数最后的局面再乘一个排列.
最后的排列数也很好算, 枚举空格个数, 方案数就是
$$
2n\sum_i \binom{n-i}{i} (n-i-1)!
$$
阶乘减一是因为前面方案数实际上是 $\dfrac{\binom{n-i}{i}}{n-i}$ , 因为插板插完是个环.
CF1111D Destroy the Colony
什么鬼题面
给一个字符串 $s$ , $q$ 次询问对于两个字符 $x, y$ , 有多少种方法可以使得每一种字符都只出现在 $s$ 的前一半或后一半, 并且 $x, y$ 处于同一边.
$\vert s \vert \le 10^5, \vert \Sigma \vert \le 52, q\le 10^5$
首先 $q\le 10^5$ 是在诈骗, 一共只有 ${ \vert s \vert }^2$ 种询问.
$n=\dfrac{ \vert s \vert }{2}$
考虑没有限制的话, 就是要我们从中选若干个数和为 $n$ 求方案数, 这个方案数乘上 ${(m! )}^2$ 再除掉 $\prod cnt_i!$ 就是没限制的答案. 有限制的时候就用从背包里删物品的做法删了再加进去一个他俩算作同一种的即可.
CF1466G Song of the Sirens
给定字符串 $s_0, t$ , 满足 $s_{i+1}=s_it_is_i$ . 多次询问, 每次询问字符串 $w$ 在指定的 $s_k$ 中的出现次数. 答案对 $10^9+7$ 取模.
$n, q\le 10^5$
考虑 $s_i$ 对询问的贡献是跨过 $t_i$ 的出现次数, 长度是 $2\vert w\vert +1$ , 用kmp, hash可以做到 $k\vert w\vert$ 回答单次询问.
那么考虑, 对于 $i, j$ , 如果 $\vert s_i\vert >\vert w\vert, \vert s_j\vert >\vert w\vert, t_i=t_j$ , 它们的贡献应该相同.
而由于每次 $s$ 长度翻一倍, 只用 $\log w$ 次就超过了, 那么复杂度就是 $\min{\log w, k} \vert w\vert$ . 结束了.
CF1400G Mercenaries
有 $n$ 个人和 $m$ 对敌对关系, 每一个人有一个条件区间 $[l_i, r_i]$ .
现在要在这 $n$ 个人中选若干个人. 定义一个合法的选择 ${S}$ , 当且仅当对于 ${S}$ 中的所有人 $i$ , $l_i\le \vert S \vert \le r_i$ , 且 ${S}$ 中所有人互不敌对.
求有多少种合法的选择, 答案对 $998244353$ 取模.
$1\le n\le 3\times 10^5$ , $0\le m\le \min{20, \frac{n(n-1)}{2}}$ , $1\le l_i\le r_i\le n$ .
考虑如果 $m=0$ , 直接枚举选的人数就做完了.
考虑容斥, 于是要求满足不限制集合 $s$ , 那么就是强制选若干点的方案数.
那么若原来我们枚举人数 $x$ 的时候方案数是 $\binom{n}{x}$ , 现在强制选了 $cnt$ 个点, 方案数就是 $\binom{n-cnt}{x-cnt}$
要对所有这个求和会寄, 但因为这个 $cnt$ 最大到 $2m$ , 所以可以直接一遍处理所有 $cnt$ , 再一遍容斥枚举点集 $O(1)$ 算, 复杂度就是 $nm+2^m$ .
CF285E Positions in Permutations
称一个 $1\sim n$ 的排列的完美数为有多少个 $i$ 满足 $\vert P_i-i \vert =1$ .
求有多少个长度为 $n$ 的完美数恰好为 $m$ 的排列. 答案对 $10^9+7$ 取模.$1 \le n \le 1000, 0 \le m \le n$ .
二项式反演. $f(n)$ 表示完美数至少为 $k$ 的方案数, $g(n)$ 表示恰好为 $k$ 的, 于是有 $f(n)=\sum_i \binom{i}{n} g(i)$ , 反演后 $g(n)=\sum_i {(-1)}^{n-i}\binom{i}{n} f(i)$ .
现在转而求钦定 $k$ 个完美位的方案数. 考虑dp. $f_{i, j, 0/1, 0/1}$ 表示值域上前 $i$ 个选了 $j$ 个, 且 $i, i+1$ 是否作为完美位, 复杂度 $n^2$ 然后乘上一个阶乘就上上文的 $f(n)$ , 反演掉即可.
CF1530F Bingo
给定一个 $n\times n$ 的表格, 表格中的每个元素有 $p_{i, j}$ 的概率为 $1$ , 否则为 $0$ .
求至少有一行或一列或一条对角线全为 $1$ 的概率. 对角线指主对角线或副对角线.
$n\le 21$
对角线看做特殊的列.
考虑容斥, 复杂度 $n\times 2^{2n+2}$ , 是不行的.
考虑只容斥列, 对于行带着容斥系数dp. 那么钦定一些列选不选之后, 这一行的系数就是没有被强制选的部分的概率的乘积, 设为 $p$ , 注意因为带着系数, 多选这一行之后应该乘 $-1$ , 两个加起来就行了.
CF1486F Pairs of Paths
给定一棵树和树上若干条路径, 求有多少个对 $i\ne j$ 满足路径 $i$ 和路径 $j$ 有且仅有一个公共点.
$n\le 3\times 10^5$
一开始糊了个强力做法, 假了, 不会.
考虑两个路径的交点一定是两个路径的lca中深的那一个.
考虑如果两个lca相同, 问题是简单的: 统计lca相同, 且路径经过的子树不同, 只要容斥算相同的就行了.
不同的做法感觉很鬼, 说的是LCA从小到大排序, 每次给小于当前lca的lca点的子树加1. , 查的时候查一下, 以lca为根的子树和减去序列两段点子树和.
另一个做法是离谱的点边容斥.
CF140E New Year Garland
现在小 $A$ 手上有 $m$ 种小球, 他要用这些小球装饰一棵圣诞树.
这是一棵神奇的圣诞树, 一共有 $n$ 层, 每层由 $l_i$ 个小球组成.
对于每一层内部, 相邻的小球的都不相同.
同时, 外部来看, 相邻的两层的小球集合不相同.
现在小 $A$ 想要知道一共有多少种合法装饰方案, 答案对 $p$ 取模.
数据范围: ( $1\le n, m\le 10^6, 2\le p\le 10^9, 1\le l_i\le 5000, \sum\limits^n_{i=1}l_i\le 10^7$ )
考虑对于一层的计数方案, 只取决于这一层能用的颜色数和这层的球总数. 数量是 $m\times (m-1)^{c-1}$ , $c$ 为能用的数量.
那么差分完了就是恰好用 $c$ 种的, 设这个为 $g(l, c)$
那就直接 $f_{i, j}$ 表示前 $i$ 层, 最后一层用了 $j$ 个颜色, 就行了吧.
$$
f_{i, j} = (\sum f_{i-1, k}) \times {m}^{\underline{j}}\times g(l_i, j) - f_{i-1, j}\times j! \times g(l_i, j)
$$
然后发现我是智障, $g(l, c)$ 不能用至多的差分得到, 关系是一个二项式反演, 这个 $g$ 还是直接递推比较好. 式子是 $g(i, j)=g(i-1, j-1)+g(i-1, j)\times (j-1)$
P5204 [USACO19JAN] Train Tracking 2 P
给出长 $n$ 的序列的每个区间 $[i, i+k-1]$ 的最小值, 求值域不超过 $10^9$ 的原序列 $a$ 的方案数, 膜 $10^9+7$ .
$n, k\le 10^5, a\le 10^9$
考虑假设所有 $c$ 都是相同的, 怎么做? 相当于每 $k$ 个就要选一个 $c$ . 然后我们设可以选的数总数是 $x+1$ (多了个 $c$ )
暴力dp就是 $f_{i, j}$ 表示前 $i$ 个, 且没选 $c$ 已经有 $j$ 个. 转移 $f_{i, j}=f_{i-1, j-1}\times x$ , 可以直接记录一下上移多少位和全局乘法标记. 就是通过数据结构优化dp做.
题解区一个老哥用等差数列写了一把, 惊叹于他的脑回路, 但还是应该积累一下这个方法, 就是对一维状态的dp可以用类似数列的方法做.
最后, 实际上可以法法塔, 是1log的.
当然重点是接下来的, 考虑 $c$ 分成若干段, 对于每个连续段, 考虑 $c_i=\ldots=c_j$ , 那么现在有 $c_{i-1}>c_i$ , 就有:
$\min {a_i\ldots a_{i+k-1}}=c_i<c_{i-1}=\min {a_{i-1}\ldots a_{i+k-2}}$
于是有 $a_{i+k-1}=c_i$ 确定下来了, 那么它前面的都可以随便选, 直接归到上一个连续段考虑即可. 后面相同的同理. 这样处理之后每一段是独立的, 最后直接乘起来就是答案. 如果一段空了那么显然不用管它们.
P3643 [APIO2016] 划艇
计数长 $n$ 的序列 $a$ , 满足要求
- 若 $a_i\ne 0, a_i\in [l_i, r_i]$
- 若 $a_i\ne 0, a_i\ge a_{i-1}$
$n\le 500, a_i\le b_i\le 10^9$
和上面CF1295F Good Contest类似吧.
仍然离散化区间, 设 $f_{i, j}$ 表示前 $i$ 个, 最后一个是 $j$ 区间的方案数, 然后不从 $i$ 转移而从 $j$ 转移, 就结束了.
CF367E Sereja and Intervals
有 $n$ 个区间, 你需要为每个区间分配左右端点, 端点属于 $[1, m]\cap \mathbb{N}$ . 你需要保证区间两两互不包含且至少存在一个区间的左端点等于 $x$ , 输出方案数对 $10^9+7$ 取模的结果, 区间有标号. $nm\leqslant 10^5$ , $1\leqslant x\leqslant m$ .
还可以吧.
考虑很显然的因为不互相包含, 所以按 $l$ 排序之后 $r$ 递增.
于是方案数是左右端点分别的方案再给一个阶乘(标号).
然后这个可以直接dp. 就直接设 $f_{i, j, k}$ 前 $i$ 个有 $j$ 个左端点 $k$ 个右端点. 复杂度就 $nm^2$
P6189 跑步
划分数. $n\le 10^5$ , 对 $p\le 2^30$ 取模.
多项式? ? ?
居然是根号分治. 设 $B=\sqrt n$
完全背包前 $B$ 个数的方案, 记结果 $g_{i}$ 表示凑 $i$ 的方案数.
dp出只有大于 $B$ 的数凑成的方案, 然后卷起来.
CF1651E Sum of Matchings
收录在greedy里
CF1613F Tree Coloring
给一棵有根树, 求排列 $c$ 的方案数使得 $\forall u, \ c_{fa}-1\ne c_u$ .
膜998244353, $n\le 250000$
原来是多项式题.
考虑钦定 $i$ 个点不合法, 直接容斥就是 $i$ 为偶数的方案减去奇数的.
二项式反演也一样. 考虑钦定 $i$ 个点不合法的方案数是 $f(i)$ , 恰好 $i$ 个点不合法的方案数 $g(i)$ , $f(i)=\sum \binom{i}{j}g(j)$ , 这个是因为 $i$ 个点不合法的方案是等价的, 于是反演得 $g(0)=\sum f(i)\times (-1)^i$ , 可以扩展到其它恰好其它 $i$ 个不对的.
那么考虑如何求 $f_i$ . 我们只需要知道从这里面选 $i$ 个不合法的方案数, 因为剩下的可以随便排, 问题就变成了钦定 $i$ 个点不合法的方案数.
考虑点 $u$ 有 $k$ 个儿子, 则在其中钦定一个不合法点的方案数是 $k$ , 钦定其中没有的方案数是1, 所以把 $1+kx$ 卷起来就行了. 分治ntt可以做 $n\log^2 n$ .
CF1580B Mathematics Curriculum
求有多少排列长度为 $n$ , 恰有 $k$ 个数满足所有包含这个数的区间中, 不同的最大值有恰好 $m$ 个.
$n\le 100, m, k\le n, p\le 10^9$
对于一个数来说, 其包含这个数的区间的不同最大值个数恰好是这个数向前向后的前缀min个数之和. 而这个等价于笛卡尔树(大根)上的层数, 所以就是计数笛卡尔树上 $m$ 层恰好有 $k$ 个元素的方案数.
考虑dp笛卡尔树的结构, 设 $f_{i, j, k}$ 表示 $i$ 个点的笛卡尔树, 深度为 $j$ 的有 $k$ 个的方案数即可.
CF1278F Cards
有 $m$ 张牌, 其中一张是王牌, $n$ 次洗牌后查看第一张牌, 看见王牌的次数 $x$ . 认为洗牌时 $m!$ 排列概率均等. 求 $x^k$ 的期望.
$n, m\le 998244353, k\le 5000$
直接推式子.
$$
\begin{aligned}
&\sum_i i^k\binom {n}{i}{(\dfrac{1}{m})}^i{(\dfrac{m-1}{m})}^{n-i} \
=&\dfrac{1}{m^n}\sum_i i^k{(m-1)}^{n-i}\binom{n}{i}\
=&\dfrac{1}{m^n}\sum_i {(m-1)}^{n-i}\binom{n}{i}\sum_j {k\brace j}i^{\underline{j}}\
=&\dfrac{1}{m^n}\sum_j{k\brace j}\sum_i{(m-1)}^{n-i}\binom{n}{i}i^{\underline{j}}\
\
&\binom{n}{i}i^{\underline{j}}=[i\ge j]\dfrac{n^{\underline{i}}}{i^{\underline{i}}}i^{\underline{j}}=\dfrac{n^{\underline{j}}{(n-j)}^{\underline{i-j}}}{(i-j)! }=n^{\underline{j}}\binom{n-j}{i-j}\
\
&\sum_i {(m-1)^{n-i}}\binom {n}{i}i^{\underline{j}}\
=&n^{\underline{j}}\sum_i \binom{n-j}{i-j}{(m-1)^{n-i}}\
=&n^{\underline{j}}\sum_i \binom{n-j}{n-i}{(m-1)^{n-i}}\
=&n^{\underline{j}}{(m+1-1)}^{n-j}\
=&n^{\underline{j}}m^{n-j}\
\
&\dfrac{1}{m^n}\sum_j{k\brace j}\sum_i{(m-1)}^{n-i}\binom{n}{i}i^{\underline{j}}\
=&\dfrac{1}{m^n}\sum_j{k\brace j}n^{\underline{j}}m^{n-j}
\end{aligned}
$$
可以枚举 $j$ 直接做了.
告诉我们要相信式子的力量.
CF1153F Serval and Bonus Problem
给定长为 $l$ 的数轴, 有 $n$ 个在 $[0, l)$ 间随机的区间, 求被被至少 $k$ 个区间覆盖的期望长度.
$k, n\le 2000, l\le 10^9$ , 膜998244353.
首先实际上 $l$ 是没用的, 按 $l=1$ 的算直接乘上就行了.
考虑位置 $x$ 被覆盖一次的概率是 $2x(1-x)$
$$
f(x)=\sum_{i\in[k, n]} \binom{n}{i}(2x(1-x))^{i} (1-2x(1-x))^{n-i}
$$
对这个求积分就是答案.
这个是关于 $x$ 的多项式, 如果直接暴力是 $n^3$ 的.
中间部分是卷积, 可以 $ntt$ 做成 $n^2\log n$ .
考虑算点值再插值回去, 最后再求积分也是可行的, 那么 $O(n^2)$ 算 $n$ 个点值就行了.
好厉害啊.
CF814E An unavoidable detour for home
$n$ 个点, 每个点有度数 $d_i$ , 构造无向图满足点 $1$ 到点 $i$ 的最短路唯一且比到 $i-1$ 的长. 求方案数.
$n\le 50, 2\le d_i\le 3$
想想以1为根的最短路树. 那么图是这个的基础上连若干同深度的边得到的.
然后dp计数. 设 $f_{i, j}$ 表示后 $i$ 个节点, 最后一层有 $j$ 个的方案数. 从下往上dp.
这里不记点的度数, 因为从下往上dp保证每个点都还有一个度留给往上的. 每个点的儿子数量不确定但父亲数量确定是从下往上的原因.
那么相邻两层之间的边, 一层内的边都分别预处理即可.
反正还是很不会数数啊.
CF382E Ksenia and Combinatorics
求有多少个以 $1$ 为根的 $n$ 节点二叉树最大匹配为 $k$ , 树相同判定为每个节点的相连节点相同.
膜 $10^9+7$
第一反应是, 很像SDOI2022D2T1吧
所以还是类似dp of dp的思路, 但注意树的最大匹配是不需要dp的, 实际上做法是直接贪心, 从叶子开始匹配, 那么这里就设 $f_{u, i, 0/1}$ 表示 $u$ 节点内有 $i$ 个匹配, 其中 $u$ 自身是否被匹配即可.
注意因为判定是树同构所以钦定左儿子小于右儿子, 大小相同除以2. 并且转移的时候要带编号.
CF235E Number Challenge
一个莫反题有贪心和组合数学标签上让人问号的.
收录在greedy中.
CF1548C The Three Little Pigs
$q$ 次给定 $x$ , 询问 $\sum_{i=1}^n \binom{3i}{x}\pmod 10^9+7$ .
$n\le 10^6, q\le 2\times 10^5, x\le 3n$
考虑那一定是对着这一堆 $x$ 一起算. 但这个式子关于 $x$ 不是多项式.
但还是简单的, $\binom{3i}{x}=[z^x] (z+1)^{3i}$ , 那么直接求和然后暴力求即可求出对所有 $x$ 的答案.
CF840C On the Bench
给定序列 $a_n$ , 求排列个数使得相邻两个的乘积不为完全平方数. 膜 $10^9+7$ .
$n\le 300, V\le 10^9$
考虑直接给所有数除掉自己的平方因子, 就成了求相邻两数不同的排列个数.
考虑把所有类的数一一插进去, 假设现在已有的排列长 $m$ , 要再插进 $k$ 个相同值, 方案数显然是 $\binom{m+1}{k}k!$ . 就结束了吧
哦暴露了垃圾的数数水平, 这个显然是错的啊///fn原因是有可能出现现在有若干个位置相邻但以后被插入了东西.
那就再加一维直接记 $f_{i, j, k}$ 表示前 $i$ 类数, 并且当前有 $j$ 个相邻的数之间需要被插入新的数, 其中有 $k$ 个是等于 $i$ 的, dp就行了. 复杂度是 $n^3$ 的. 这个dp转移比较像那种连续段dp.
有个更厉害点的做法, 考虑仍然容斥, 那么钦定 $i$ 对彼此相邻的方案数记为 $f_i$ , 注意确实满足方案数只和钦定相邻的个数有关, 那么显然答案就是 $\sum f_i\times (-1)^i$ , 而 $f_i$ 可以由各个颜色的直接卷积合并. 复杂度 $n^2$ .
CF997C Sky Full of Stars
给定 $n\times n$ 的正方形网格, 用三种颜色染色, 求没有一行或一列颜色相同的方案数. 膜998244353.
$n\le 10^6$
看到这种直接考虑容斥反演类技术. 于是钦定选了 $i$ 行 $j$ 列颜色相同方案数是 $f(i, j)$ , 没有相同的方案数就是
$$
\sum_i \sum_j f(i, j)\binom{n}{i}\binom{n}{j}\times (-1)^{i+j}
$$
(高维容斥反演时系数是各维度之积, 也可以分部理解)
考虑 $f$ 是十分容易计算的:
$$
f(i, j)=
\begin{cases}
3^{(n-i)(n-j)+1}, \ ij\ne 0\
3^{i+j}3^{n(n-i-j)}\ ij=0
\end{cases}
$$
发现 $ij=0$ 的情况可以直接单独计算(此时只有一个变量, 直接暴力求). 考虑 $ij\ne 0$ 的情况:
$$
\begin{aligned}
&\sum_i \sum_j \binom{n}{i}\binom{n}{j}\times (-1)^{i+j}\times 3^{(n-i)(n-j)+1}\
=&\sum_i \sum_j \binom{n}{i}\binom{n}{j}\times (-1)^{i+j}\times 3^{ij}3^{ni}3^{nj}3^{n^2+1}\
=&3^{n^2+1}\sum_i (-1)^i \binom{n}{i}3^{ni} \sum_j \binom{n}{j}(-1)^j\times 3^{nj}\times 3^{ij}
\end{aligned}
$$
$ij$ 不会处理了. 大多数组合恒等式这里不行因为这个次幂很难看, 考虑少数有正常幂的二项式定理
$$
\begin{aligned}
&3^{n^2+1}\sum_i (-1)^i \binom{n}{i}3^{ni} \sum_j \binom{n}{j}(-1)^j\times 3^{nj}\times 3^{ij}\
=&3^{n^2+1}\sum_i (-1)^i \binom{n}{i}3^{ni} \sum_j \binom{n}{j}(-1\times 3^{n+i})^j\
=&3^{n^2+1}\sum_i (-1)^i \binom{n}{i}3^{ni} (-1\times 3^{n+i}+1)^n
\end{aligned}
$$
就结束了.
CF1327F AND Segments
给定 $n, k, m$ 以及 $m$ 个限制 $(l_1, r_1, x_1)\ldots (l_m, r_m, x_m)$
求每个数都在 $[0, 2^k]$ 中, 且 $\forall i, a_{l_i}\operatorname{ans} a_{l_i+1}\operatorname{ans}\ldots a_{r_i}=x$ , 且长度为 $n$ 的序列个数
$n, m\le 5\times 10^5, k\le 30$
膜998244353
考虑每一位是相同的. 问题变成了, 指定一段全是1或者其中至少有一个0, 求方案数.
那直接用全1段把它们拆成若干段, 每段就只有限制至少有一个0的方案了.
可以设 $f_i$ 表示前 $i$ 个且第 $i$ 个为0的方案数, 则 $f_i$ 是一个区间的和, 前缀和优化即可.
CF1174E Ehab and the Expected GCD Problem
关于排列 $p_n$ , 设 $g_i$ 表示 $\gcd {a_1, a_2, \ldots, a_i}$ , $g_i$ 的数量为 $f(p)$ , $f$ 的最大值为 $f_max$ , 求有多少个排列 $p$ 满足 $f(p)=f_max$
$n\le 10^6$
考虑 $f$ 的最大值, 显然一种构造是从头开始2的幂下降一定能达到最大. 于是最大值已知.
那么也能顺便得到结论: 不会有 $5$ 及以上的下降(下降指前缀 $\gcd$ 除以了 $5$ ), 不会有两个 $3$ 的下降, 因为都可以调整为数量更多的 $2$ 下降.
于是直接dp, $f_{i, j, k}$ 表示前 $i$ 个, 其中当前gcd为 $2^i3^j$ 的方案数, 从序列维转移.
dp排列值域扫多了都要忘了能序列了.
CF1367F Flying Sort
给定 $n$ 个正整数构成的序列, 每次可以将序列中的任意一项放到最前面或最后面, 求最少操作次数让序列不降.
Easy Version
保证每个数互不相同, $n\le 3000$
每个数最多操作一次. 显然.
那么找到可以保留的最多的数. 并且因为中间不能插进数, 所以就是保留最长的相差为1的上升的子序列. 设 $f_i$ 表示前 $i$ 个以 $i$ 结尾的答案, 那么 $f_{a_i}=f_{a_i-1}+1$
Hard Version
可以有相等的数, $n\le 2\times 10^5$
首先你觉得这个就是直接把上面的dp搬过来, 加上可以相等.
但实际上区别在于, 中间可能要取完, 比如排列1 1 2 2 3 3 2中, 我们不能选1 1 2 2 3 3因为这样2是插不进来的.
所以就是分三种情况: 都等于一个值, 两段不一定取完, 三段, 其中中间段必须取完这三种, dp即可.
CF510D Fox And Jumping
给出 $n$ 张卡片, 分别有 $l_i$ 和 $c_i$ . 在一条无限长的纸带上, 你可以选择花 $c_i$ 的钱来购买卡片 $i$ , 从此以后可以向左或向右跳 $l_i$ 个单位. 问你至少花多少元钱才能够跳到纸带上全部位置. 若不行, 输出 $-1$ .
$n\le 300, l_i\le 10^9$
能从0到1等价于能完成任务. 考虑若干数凑出1等价于它们 $\gcd$ 为1, 直接冲用map记状态就行.
BZOJ3864 Hero meet devil
给定 $s$ , 求有多少长 $m$ 的串 $t$ 满足 $lcs(t, s)=i$ , 对所有 $i$ 输出答案.
$\vert s\vert \le 15, m\le 1000$
内层dp显然是求lcs的dp $f_{i, j}$ 表示 $s$ 前 $i$ 个和 $t$ 前 $j$ 个那个, 是众所周知的, 关键是如何压缩状态.
发现做到 $2^{\vert s\vert}m$ 左右可能正好? 考虑我们显然扫描 $j$ , 维护所有 $f_{i}$ , 和LCS Again那题一样有个经典结论 $f_{i, j}-f_{i, j-1}\le 1$ 所以可以差分压成二进制就做完了.
CF1043F Make It One
给定序列 $a_n$ , 求选最少的数使得它们gcd为1.
$n, a_i\le 3\times 10^5$
考虑 $3\times 10^5$ 内的数的最多不同质因数个数有 $6$ 个.
那么答案最大是不是不超过 $6$ 呢.
发现实际上界是7, 构造出来应该是 $2, 3, 5, 7, 11, 13, 17$ 分别删去一个数得到的集合.
qyc给出强力做法: 直接gcd卷积, 若答案为 $k$ , 则卷恰好 $k$ 次的时候 $f_1\ne 0$ .
复杂度是 $n\log n$ 或 $n \log^2 \log n$
CF1792F1 Graph Coloring (easy version)
给定$n$个点的完全图,求有多少个红蓝染色方案,使得对任意一个点集$S$,满足其导出子图仅看红色边是连通的,或满足仅看蓝色边上连通的,但不0同时满足两个限制.
$n\le 5000$
还挺厉害
[conclusion] 一个图和它的补图中至少有一个是连通的.
对于原图中不连通的两个联通块,其中一个的点$x$必然和另一个的所有点相连,所以这个连通块在补图中是连通的,剩下部分显然.
整张图必然是蓝/红连通的,假设是红连通,蓝不连通.
那么考虑计数策略之一,看所有和$1$蓝连通的点组成的块,组成了一个规模更小的问题,而剩下的点和这个块之间全是红边,剩下的点是另一个规模更小的问题,可以$n^2$dp出来.
$$
f_n=\sum_{x<n} \binom{n,x} f_x \cdot (f_{n-x}\cdot (2-[x=n-1]))
$$
$n-x$的部分可能是蓝连通的也可能是红连通的,但当只有一个点的时候就只有一种了.
CF1781F Bracket Insertion
进行$n$次操作,设当前序列为$s$(初始为空),每次从$s$中随机选一个空位(若长度为$k$,有$k+1$个空位),以$p$概率插入
()或以$1-p$概率插入)(,求最后得到合法序列的概率.膜$998244353$.
$n\le 500$.
考虑把插入的包含关系建树,设()是$1$,)(是$-1$,看起来要求任意根开始的路径和非负.
那考虑dp,设$f_{i,j}$表示$i$个点,节点到当前根的和最小为$j$的方案数dp应该就行.
4. 其他
[Nowcoder某题](https: //ac. nowcoder. com/acm/contest/42819/E)
$n$ 行 $2n$ 列的网格图, 每行每列最多有两个棋子, 求本质不同方案数.
本质相同定义为可以通过交换若干行列得到相同的方案.
$n\le 10^5$ , 膜998244353
汪娟介绍的
考虑这是一个经典网络流模型, 可以把一个方案对应到一个二分图上(建行点列点, 有棋子则连对应行列).
于是变成计数无标号二分图个数, 并且每个点度数不超过2, 一边 $n$ 个点一边 $2n$ 个点.
发现因为度数限制, $n$ 个点这边怎么选 $2n$ 个点都够用, 所以可以只考虑左边的大小, 视右边大小为无限.
那么度数限制为 $2$ 的二分图只有链和环两种. 那么就是计数若干个链和环且左边为 $n$ 个点.
然后在仅考虑左边点的情况, 它们的区别仅在于左边至少一个点(左边点少的链, 左右数量相等的链, 环)或者至少两个点(左边数量多一个的链), 所以写成生成函数就是 $\prod_{i=1} \dfrac{1}{1-x^k} * \prod_{i=2} \dfrac{1}{1-x^k}$
一个简单做法是分治ntt或ln+exp.
常数小做法是五边形数四次方乘 $1-x$ . 复杂度 $n\log n$ .
CF930E Coins Exhibition
有 $k(1 \leq k \leq 10^9)$ 个硬币, 每个硬币有正面朝上和反面朝上两种状态.
现有 $n+m(0 \leq n, m \leq 10^5)$ 个限制条件, 每个限制条件形如 $(l_i, r_i)(1 \leq l_i \leq r_i \leq k)$ . 前 $n$ 个限制条件限制区间 $[l_i, r_i]$ 内至少有一个硬币正面朝上, 后 $m$ 个限制条件限制区间 $[l_i, r_i]$ 内至少有一个硬币反面朝上.
问共有多少种摆放硬币的方案使得所有限制条件都被满足. 答案对 $10^9+7$ 取模.
考虑dp, $k$ 这么大肯定要离散化, 不过先想一个关于 $k$ 线性的东西, 考虑限制是在说一个什么, 序列上数数自然设 $f_{i, 0/1}$ 表示前 $i$ 个最后一个是 $0/1$ 的方案, 那么想到钦点从最近的0/1转移, 于是发现一个限制 $[l, r]$ 中至少一个0等价于对于大于等于 $r$ 的位置其找0的时候需要在 $l$ 之后, 那么前缀和优化就线性了. 最后上一个划艇的套路: 离散化区间即可.
我天, 不会写dp了.
