2022/04/19 做题记录

前夕

设 $G_i={n \choose i}2^{2^{n-i}}$ 为钦定 i 个元素在交集中的方案数，但由于 n 太大没有办法直接二项式反演。

考虑构造容斥系数 $\alpha(i)$ 使得 $\sum_{j=0}^{i} {i \choose j} \alpha(j) = [4|i]$，这样答案就是 $\sum_{i=0}^n G(i)\alpha(i)$ ,考虑把第一个柿子二项式反演，得到 $\alpha(i) = \sum_{j=0}^i (-1)^{i-j} {i \choose j}[4|j]$ ，对后面那个式子单位根反演一下得到 $\alpha(i) = \sum_{j=0}^i (-1)^{i-j} {i \choose j} \sum_{k=0}^3w_4^{jk}=\frac{1}{4}\sum_{k=0}^3\sum_{j=0}^i{i \choose j}(-1)^{i-j}(w_4^k)^j=\frac{1}{4}\sum_{k=0}^{3}(w_4^k-1)^i$

,其中 $w_4$ 为 4 次单位根，因为答案模 998244353 这里直接用原根算就行。

注意一下全不选的情况。

code: /code/2022.4.19/ac10387.cpp

PYXFIB

设 $F_i = A^i$，其中 A 是个矩阵并且容易得到。

原式=$\sum_{i=0}^n [k|i] {n \choose i} A^i=\sum_{i=0}n {n \choose i} A^i \frac{1}{4}\sum_{j=0}^{k-1}w_k{ij}=\frac{1}{4}\sum_{i=0}^{{k-1}\sum_{j=0}}n{n \choose j} A^j (w_{k}ⁱ⁾j=\frac{1}{4}\sum_{i=0}^{k-1}(a*w_ki)^n $

，因为 $k|(p-1)$ 所以也可以用原根算。

code: /code/2022.4.19/bz3328.cpp

P4929

DLX 模版。

code: /code/2022.4.19/P4929.cpp

[JSOI2012] 分零食

设欢乐程度的生成函数为 $F(x)$,这里认为常数项为 1，那么答案就是：

$$[x^m]\sum_{i=0}^k{F^i}(x) =\frac{F^{k+1}-1}{F(x)-1}$$

直接多项式求逆即可，模数虽然不是 NTT 模数，但 $255*255*10000<998244353$，于是每乘一次求一次模就行（因为这样多个多项式连乘需要拆开算！），而分母多项式常数项为 -1 所以求逆元也没有问题（就是本身）。

code: /code/2022.4.19/P5075.cpp