考虑将二项式反演的符号化方法扩展到斯特林反演上。
染色问题
现有一排 \(n\) 个格子,每个格子皆可涂成 \(c\) 种颜色之一。
给定集合 \(W\),定义一个染色合法当且仅当:对于任意格子,记和它颜色相同的格子有 \(x\) 个(包括自身),必有 \(x\in W\)。
求有多少合法的染色方案。
可以直接用 EGF 推导:单个颜色的 EGF 为 \(F(z)=1+\sum\limits_{k\in W}\frac{x^k}{k!}\),答案是 \(\big[\frac{x^n}{n!}\big]F^c(z)\)。
接下来展示斯特林容斥的推理方法。
记 \(\mathcal S\) 为带染色的集合划分,且集合大小在 \(W\) 中。
记 \(\mathcal S^{\rm col}\) 为带染色的集合划分,满足集合的颜色各不相同(缤纷),且集合大小在 \(W\) 中。\(|\mathcal S^{\rm col}_n|\) 即为答案。
记 \(\mathcal S_0\) 为有标号集合,集合大小在 \(W\) 中。(无色透明)有 \(S_0(z)=\sum_{k\in W}\frac{x^k}{k!}\)。
记 \(\mathcal D\) 为带染色的有标号无序集。
记 \(\mathcal D^{\rm col}\) 为带染色的有标号无序集,且元素的颜色各不相同(缤纷)。
根据“子结构构造”的组合意义,用有标号非空集合(无色透明)替换 \(\mathcal D\) 的元素(并继承其颜色),有
\[\begin{aligned} \mathcal S&=\mathcal D\boxtimes \mathcal S_0\\ \mathcal S^{\rm col}&=\mathcal D^{\rm col}\boxtimes \mathcal S_0 \end{aligned} \]观察 \(\mathcal D\) 是如何从 \(\mathcal D^{\rm col}\) 生成的,根据二项式反演的经验,我们最好让任意一个 \(d'\in\mathcal D\) 对应到唯一一个 \(d\in D^{\rm col}\),然后再考虑反射。
对任意一个 \(d'\in\mathcal D\),将同色的元素合并,就满足各个元素颜色不同。反之,对任意一个 \(d\in \mathcal D\),可以将其中的每个元素扩增若干倍(每个元素换成任意大的纯色非空集合),这样能得到 \(\mathcal D\) 中的所有元素。
具体地,设 \(\mathcal D_0\) 为有标号非空无序集合(无色透明)(\(D_0(u)=e^u-1\)),根据“子结构构造”
\[\mathcal D=\mathcal D^{\rm col}\boxtimes \mathcal D_0 \]翻译为 EGF,得
\[\begin{aligned} D(u)&=\sum_{k=0}^{+\infty}\dfrac{c^ku^k}{k!}=e^{cu}\\ D(u)&=D^{\rm col}(D_0(u))=D^{\rm col}(e^u-1)\\ D^{\rm col}(u)&=D(\ln(1+u))=(1+u)^c\\ S(z)&=D(S_0(z))=\big(1+S_0(z)\big)^c\\ \end{aligned} \]其中 \(e^u-1\) 的复合逆是 \(\ln(1+u)\)。
由于本题的特殊性,其实也可以直接求出 \(D^{\rm col}(u)\)。注意到 \(k\) 个缤纷的有标号元素方案数为 \(c^{\underline k}\),得
\[D^{\rm col}(u)=\sum_{k=0}^{+\infty}\frac{c^{\underline k}x^k}{k!}=\sum_{k=0}^c\binom{c}{k}x^k=(1+u)^c \]Loj6728 U 群把妹王
现有 \(n\times m\) 个格子,每个格子皆可涂成 \(c\) 种颜色之一。
给定集合 \(W_1,W_2\),定义一个染色合法当且仅当:
- 对于任意一行,记和它图案相同的行有 \(x\) 个(包括自身),必有 \(x\in W_1\)。
- 对于任意一列,记和它图案相同的列有 \(x\) 个(包括自身),必有 \(x\in W_2\)。
求有多少合法的染色方案。
这是上一题的扩展版本。
记 \(\mathcal S\) 为:将行列划分,行集合大小在 \(W_1\) 中,列集合大小在 \(W_2\) 中,每个行集合相等,每个列集合相等。
记 \(\mathcal S^{\rm col}\) 为:在 \(\mathcal S\) 的基础上,要求行列的划分均是缤纷的。
记 \(\mathcal D\) 为:一对带染色有标号无序集(分别管理行和列,每个元素管控一个行/列集合)。
记 \(\mathcal D^{\rm col}\) 为:在 \(\mathcal D\) 的基础上,要求行列均是缤纷的。
记 \(\mathcal S_1\) 为有标号行集合,集合大小在 \(W_1\) 中;\(\mathcal S_2\) 为有标号列集合,集合大小在 \(W_2\) 中(均无色透明),则有
\[\begin{aligned} \mathcal S&=\mathcal D\boxtimes(\mathcal S_1,\mathcal S_2)\\ \mathcal S^{\rm col}&=\mathcal D^{\rm col}\boxtimes(\mathcal S_1,\mathcal S_2) \end{aligned} \]即:将一个行集合换成若干行,一个列集合换成若干列。
设 \(\mathcal D_1\) 为有标号非空无序行集合,\(\mathcal D_2\) 为有标号非空无序列集合(均无色透明),根据“子结构构造”
\[\mathcal D=\mathcal D^{\rm col}\boxtimes(D_1,\mathcal D_2) \]即:将行列(集合)分别复制若干次。
用 \(u,v\) 表示行列,写出 EGF 得
\[\begin{aligned} S_1(u)&=\sum_{k\in W_1}\frac{u^k}{k!}\\ S_2(v)&=\sum_{k\in W_2}\frac{v^k}{k!}\\ D(u,v)&=\sum_{n=1}^{+\infty}\sum_{m=1}^{+\infty}c^{nm}\dfrac{u^nv^m}{n!m!}\\ D(u,v)&=D^{\rm col}(e^u-1,e^v-1)\\ D^{\rm col}(u,v)&=D\big(\ln(1+u),\ln(1+v)\big)\\ S^{\rm col}(u,v)&=D^{\rm col}(S_1(u),S_2(v))\\ &=D\big(\ln(1+S_1(u)),\ln(1+S_2(v))\big)\\ \end{aligned} \]难以写出 \(D(u,v),S^{\rm col}(u,v)\) 的封闭形式,但注意到只需要 \(\big[\frac{u^nv^m}{n!m!}\big]\) 系数,提取之
\[\begin{aligned} [\tfrac{u^nv^m}{n!m!}\big]S^{\rm col}(u,v) &=[\tfrac{u^nv^m}{n!m!}\big]\sum_{i=1}^{+\infty}\sum_{j=1}^{+\infty}c^{ij}\dfrac{\ln^i(1+S_1(u))\ln^j(1+S_2(v))}{i!j!}\\ &=\sum_{i=1}^{+\infty}\sum_{j=1}^{+\infty}c^{ij}[\tfrac{u^n}{n!}\big]\dfrac{\ln^i(1+S_1(u))}{i!}[\tfrac{v^m}{m!}\big]\dfrac{\ln^j(1+S_2(v))}{j!}\\ &=\sum_{i=1}^{+\infty}\sum_{j=1}^{+\infty}c^{ij}f_{n,i}g_{m,j} \end{aligned} \]其中 \(f_{n,i}=[\tfrac{u^n}{n!}\big]\dfrac{\ln^i(1+S_1(u))}{i!},\ g_{m,j}=[\tfrac{v^m}{m!}\big]\dfrac{\ln^j(1+S_2(v))}{j!}\)。这是“幂的横截”,可以用拉格朗日反演计算,需要用到复合逆,可以 \(O(|W|n\log n)\) 牛迭求出。
然后利用 \(c^{ij}=c^{\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}}\),即可做到一次卷积
\[\begin{aligned} [\tfrac{u^nv^m}{n!m!}\big]S^{\rm col}(u,v) &=\sum_{i=1}^{+\infty}\sum_{j=1}^{+\infty}c^{\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}}f_{n,i}g_{m,j}\\ &=\sum_{k=2}^{+\infty}c^{\binom{k}{2}}\sum_{i=1}^kc^{-\binom{i}{2}}f_{n,i}c^{-\binom{k-i}{2}}g_{m,k-i}\\ \end{aligned} \]后半部分和式可以卷积。
标签:big,sum,eps,反演,炫酷,mathcal,集合,rm,col From: https://www.cnblogs.com/whisper6/p/17590699.html