做题笔记 - 多项式入门

拱辰封仪(华中地区邀请赛 19th)

难点在卡常。你怎么也是二分图。注意到 $O$ 是魔法总和为奇数，也就是为魔法值为奇数的元素共有奇数个，不难想到对这个能不能进行 $-1$ 的赋权操作。注意到

$$E^2-O^2$$

可以因式分解成：

$$(E+O)(E-O)$$

。前者相当于所有方案数，后者就是对所有魔法值为奇数的元素进行 $-1$ 赋权了。在进行生成函数卷积的时候，前者系数为 $1$，后者为 $-1$。

两点之间存在奇数的路径，不仅满足两点处于同一连通块中，且满足下列条件之一：

• 该联通子图为非二分图，即存在奇环。
• 该联通子图为二分图，且两点分属左部和右部。

不难发现对于不同的连通块之间的贡献相互独立。相同连通块中，若该连通块为非二分图，则该连通块最多选出一个点；若为二分图，则左部和右部不能同时选点。

接下来刻画一下生成函数状物。对于非二分图，生成函数必然形如 $(1+px)$。对于二分图而言，左部和右部的贡献分开算，然后由于在该连通块中两者是相互独立切不能叠加产生贡献，所以最后把左部右部生成函数加起来。注意 $f_0$ 实际上被加了 $2$ 次，但是考虑到空集在左部右部图的意义一模一样，所以需要记得将 $f_0$ 减去 $1$。

对于单独的一部图，在 $(E+O)$ 里每个元素的贡献是 $(1+x)$。元素叠加贡献即 $(1+x)^{|S|}$。然后这里有一个优化是，可以直接通过预处理组合数直接算 $(1+x)^{|S|}$ 的系数，不用将 $|S|$ 个 $(1+x)$ 进行合并。

在 $(E-O)$ 需要考虑 $a_i$ 为奇数的情况，不难发现 $a_i$ 为奇数的贡献是 $(1-x)$。元素叠加贡献即 $(1+x)^{|S_{\text{even}}|}(1-x)^{|S_{\text{odd}}|}$。这也是可以用组合数分开处理的。处理完合并两个函数即可。

合并多个生成函数时，我们通过合并大小最小的两个函数以做到像启发式合并一样地优化复杂度。这个东西叫做 Huffman 式顺序合并。感兴趣的读者可以去维基百科上搜一下。时间复杂度证明类似启发式合并。

NTT 的部分，那我问你，你都做到这题了，不会 NTT 说不过去吧。

卡常的部分就各位各显神通了吧。强烈要求出题人加大时限。