LOJ3120「CTS2019 | CTSC2019」珍珠

只是想要祭奠做的时候死去的我

约定下文中的$d$为题目中的$D$

Part1

先从最最暴力的定义转移(可以跳过这个)

$S$表示个数为奇数的颜色集合

转移多项式(集合幂指数)$F(x)=\sum_0^d x^{ \{i\} }$

$\text{FWT}$得到

$F’(x)=\sum (d-2|S|)x^S$

$(F(x)^n)’=\sum (d-2|S|)^nx^S$

$\text{IFWT}$得到

$2^d F(x)^n=\sum_S \sum_T (-1)^{|S\cap T|}(d-2|T|)^n x^{S} $

答案就是

$2^d Ans=\sum_S\sum_T(-1)^{|S\cap T|}(d-2|T|)^n[|S|\leq Lim]$

如果枚举$|S|,|T|,|S\cap T|$进行统计，会出现3个元，无法直接优化到$O(n\log n)$

---

Part2

设最后得到每一种颜色的个数为$c_i,\sum c_i=n$

方案数就是$\frac{n!} {\Pi c_i!}$，很符合指数型生成函数吧

考虑最朴素的生成函数表示法，考虑每种颜色的选的个数

个数无限制的生成函数$F_0(x)=\sum \frac{x^i} {i!}=e^x$

个数为奇数的生成函数$F_1(x)=\frac{x^{1} } {1!}+\frac{x^{3} } {3!}+\cdots=\frac{e^x-e^{-x} } {2}$

个数为偶数的生成函数$F_2(x)=\frac{x^0} {0!}+\frac{x^2} {2!}+\cdots=\sum \frac{e^x+e^{-x} } {2}$

$F_1^i=2^{-i}\sum (-1)^jC(i,j)e^{(i-2j)x}$

$F_2^i=2^{-i}\sum C(i,j)e^{(i-2j)x}$

设选中$i$个奇数的答案为$G_i$

$G_i=n!C(n,i)[x^n]F_1^iF_2^{d-i}$

$=n!C(n,i)[x^n]2^{-d}\sum_j\sum_k C(i,j)(-1)^je^{(i-2j)x} C(n-i,k)e^{(n-i-2k)x}$

代$e^{ax}=\sum \frac{(ax)^i} {i!}$，约去$n!$

$=C(n,i)[x^n]2^{-d}\sum_j\sum_k C(i,j)C(n-i,k)(-1)^j (n-2k-2j)^n$

诶好像和Part1一样。。。

暴毙结束。。。。

---

Part3

上面这两种方法都要枚举三个元，无法优化，所以考虑先重复计算，再容斥掉

计算$\ge i$个方案数，然后容斥回去

设最终答案序列为$H$

我们可以快速求出选中$i$个奇数且带重复的方案数$G_i$

$G_i=\sum C(j,i)H_j=[x^n]C(d,i)F_1(x)^iF_0(x)^{d-i}$(强制选$i$个剩下未知)

$G_i=C(d,i) \cdot n! \cdot [x^n]\sum (-1)^je^{(d-2j)x}\cdot C(i,j)\cdot {2^{-i} }$

代$e^{ax}=\sum \frac{(ax)^i} {i!}$，约去$n!$

$G_i=C(d,i) \cdot \sum (-1)^j(d-2j)^n\cdot C(i,j)\cdot {2^{-i} }$

卷积一次可以得到$G$

最后的容斥就是二项式反演

$H_i=\sum_{j\ge i}(-1)^{j-i}G_jC(j,i)$

再卷积求出$H$