更^{2+eps}炫酷的反演魔术
command_block
·
·
个人记录
- 参考资料：x义x: 更炫酷的反演魔术，x义x: 更更炫酷的反演魔术
考虑将二项式反演的符号化方法扩展到斯特林反演上。
可以直接用 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。
这是上一题的扩展版本。
记 \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}
后半部分和式可以卷积。