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\)