容斥原理

洛谷题库 P6031 Cards 加强版

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

这是某场模拟考试给出的部分分: SubtaskConstraintsPointsDependencies1n,m,k522k=123k5000101,24m1001015nk56k105101,2,37k5×106201,2,3,684117 \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日

AGC058D – Yet Another ABC String

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

考虑容斥。直接钦定指定数量的位置不合法,其方案是难以计算的。又因为容斥系数是 (1)c(-1)^ccc 为钦定的非法位置数量,那么将整个串分成若干个部分分别计算方案,带上容斥系数相乘后累加,结果不变。故而尝试从上文的链入手:易得对于固定长度的一条链,能够连成它的非法位置集合不变。设 f(l,0)f(l,0) 表示“大小为偶数,且能够连成长度恰为 ll 的链”的非法位置集合数量;f(l,1)f(l,1) 则是大小为奇数。染色方案位置集合方案是独立的;则设整个串按顺序被分成了链 (l1,l2,,ls)(l_1,l_2,\cdots,l_s)(此处的“链”长度均不小于 33),答案即为 (l1,,ls)染色方案数((l1,,ls))i=1s((1)f(li,1)+f(li,0))\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日

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

代数推导

转化为容斥模型

题目所给限制可以表述为,aabb 均为单调不降的序列,长度相等(记为 kk),且 a1=0,ak=n,b1=0,bk=m,i[2,k],ai=ai1bi=bi1a_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}

考虑差分序列 ai=aiai1(i[2,k]){a_i}’=a_i-a_{i-1}\quad(i\in[2,k])bi{b_i}’ 同理,它与原序列形成双射。于是不存在 ai=bi=0{a_i}’={b_i}’=0 的差分序列合法。考虑 i=2kai=n\sum_{i=2}^{k}{a_i}’=n,也就是和为 nnk1k-1 元线性方程组的一组非负整数解;bb’ 同理。容易计算“钦定至少有 cc 个位置不合法”的方案数——利用容斥原理即可得到长为 kk 的合法序列对个数为 c=0k2(k1c)(n+(k1)1c(k1)1c)(m+(k1)1c(k1)1c)(1)c\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 答案累加上式结果 ×k\times k(更多…)

More
  • 2022年12月1日

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

g(i,j,k)g(i,j,k)表示“每个位置有ii类元素可选,且序列中必须包含指定的jj类元素的,长度为kk的序列的个数”。形式化地讲,我们需要统计满足以下条件的序列的个数:p[1,k],apS (S=i);bTS (T=j),p[1,k],ap=b\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,,j0,1,2,\dots,jTT中的元素没有被包含在序列中的序列的个数,然后乘上容斥系数累加既是答案。也即: g(i,j,k)=x=0j(1)x(jx)(ix)kg(i,j,k)=\sum\limits_{x=0}^{j}(-1)^x\dbinom{j}{x}(i-x)^{k}。通俗地讲,我们在 jj 个元素中选择 xx 个,并强制使得它们不出现在序列中,其余元素任选。除去组合数的预处理时间,复杂度为O(j)\mathrm{O}(j)。参阅AtCoder ABC 194 F – Digits Paradise in Hexadecimal可以使用上述计算而非DP求解(虽然DP更加简洁直观)

(更多…)

More
  • 2022年3月4日