容斥原理归档 – Charles Wu的博客

对于每一轮对局的 $m!$ 种排列，对于编号为 $a$ 的牌，恒有 $(m-1)!$ 种是以牌 $a$ 为首的。因此一轮可以归为 $m$ 种情况，首张为王牌的概率为 $\frac{1}{m}$ 。

这是某场模拟考试给出的部分分： $\begin{array}{cccc} \text{Subtask}&\text{Constraints}&\text{Points}&\text{Dependencies}\\ \hline 1&n,m,k\leq 5&2&\\ 2&k=1&2&\\ 3&k\leq 5000&10&1,2\\ 4&m\leq 100&10&1\\ 5&n\leq k&5&\\ 6&k\leq 10^5&10&1,2,3\\ 7&k\leq 5\times 10^6&20&1,2,3,6\\ 8&&41&1\sim 7 \end{array}$ （更多…）

More

2023年1月31日

组合数学 / 题解

AtCoder AGC058D – Yet Another ABC String – 题解

AGC058D – Yet Another ABC String

将 $\mathtt{A,B,C}$ 换成 $0,1,2$ 。记 $a,b,c$ 是题面中 $\mathtt{A,B,C}$ 的数量， $n=a+b+c$ 。我们称位置 $i$ 不合法，当且仅当 $S_{i-2}+2\equiv S_{i-1}+1\equiv S_i\pmod 3$ 。将其视为两条边 $(i-2,i-1),(i-1,i)$ ，那么所有不合法的位置造成的连边将会形成若干条链。

考虑容斥。直接钦定指定数量的位置不合法，其方案是难以计算的。又因为容斥系数是 $(-1)^c$ ， $c$ 为钦定的非法位置数量，那么将整个串分成若干个部分分别计算方案，带上容斥系数相乘后累加，结果不变。故而尝试从上文的链入手：易得对于固定长度的一条链，能够连成它的非法位置集合不变。设 $f(l,0)$ 表示“大小为偶数，且能够连成长度恰为 $l$ 的链”的非法位置集合数量； $f(l,1)$ 则是大小为奇数。染色方案与位置集合方案是独立的；则设整个串按顺序被分成了链 $(l_1,l_2,\cdots,l_s)$ （此处的“链”长度均不小于 $3$ ），答案即为 $\sum_{(l_1,\cdots,l_s)}\operatorname{染色方案数}\left((l_1,\cdots,l_s)\right)\prod_{i=1}^s\left((-1)f(l_i,1)+f(l_i,0)\right)$ （更多…）

More

2022年12月16日

OI / 组合数学 / 题解

CF1747E – List Generation – 题解

这道破题拖了我整整一天。

代数推导

转化为容斥模型

题目所给限制可以表述为， $a$ 和 $b$ 均为单调不降的序列，长度相等（记为 $k$ ），且 $a_1=0,a_k=n,b_1=0,b_k=m,\nexists i\in[2,k],a_i=a_{i-1}\land b_i=b_{i-1}$ 。

考虑差分序列 ${a_i}’=a_i-a_{i-1}\quad(i\in[2,k])$ ， ${b_i}’$ 同理，它与原序列形成双射。于是不存在 ${a_i}’={b_i}’=0$ 的差分序列合法。考虑 $\sum_{i=2}^{k}{a_i}’=n$ ，也就是和为 $n$ 的 $k-1$ 元线性方程组的一组非负整数解； $b’$ 同理。容易计算“钦定至少有 $c$ 个位置不合法”的方案数——利用容斥原理即可得到长为 $k$ 的合法序列对个数为 $\sum_{c=0}^{k-2}\binom{k-1}{c}\binom{n+(k-1)-1-c}{(k-1)-1-c}\binom{m+(k-1)-1-c}{(k-1)-1-c}(-1)^c$ 答案累加上式结果 $\times k$ 。（更多…）

More

2022年12月1日

OI

随记 – 三月四日 – DP求解强制包含部分元素的序列计数问题

被这玩意卡了一上午——前天CSP-S模拟的T4需要用到这类问题的转移。~~为什么题解TMD是错的？~~

即 $g(i,j,k)$ 表示“每个位置有 $i$ 类元素可选，且序列中必须包含指定的 $j$ 类元素的，长度为 $k$ 的序列的个数”。形式化地讲，我们需要统计满足以下条件的序列的个数： $\forall p \in [1,k], a_p \in S\space(|S|=i); \forall b \in T \subseteq S\space(|T|=j), \exists p \in [1,k], a_p=b$ 。

通过容斥原理，我们可以计算出至少有 $0,1,2,\dots,j$ 个 $T$ 中的元素没有被包含在序列中的序列的个数，然后乘上容斥系数累加既是答案。也即： $g(i,j,k)=\sum\limits_{x=0}^{j}(-1)^x\dbinom{j}{x}(i-x)^{k}$ 。通俗地讲，我们在 $j$ 个元素中选择 $x$ 个，并强制使得它们不出现在序列中，其余元素任选。除去组合数的预处理时间，复杂度为 $\mathrm{O}(j)$ 。参阅AtCoder ABC 194 F – Digits Paradise in Hexadecimal，可以使用上述计算而非DP求解~~（虽然DP更加简洁直观）~~。