DFT 处理循环卷积 + 状压 dp.
Source: Topcoder 2016 TCO Algorithm Round 3B Hard
有 $n$ 个人, 第 $i$ 个人有一个长度为 $k$ 的石头剪刀布字符串 $S_i$ ,由
R,S,P三种字符组成,表示每次比赛的选择.
建一个 $n$ 个点的新图,每个点对应一个人.
两个人之间有边当且仅当不管字符串怎么循环移位,两个人进行 $k$ 次比赛后的胜场数和负场数不变.
求这个新图中团的个数, $n\le 10^5,k\le 18$ .
考虑如何判定 $A,B$ 两个人在图中是否有边.
对 $A$ 构造一个多项式 $A(x)$ ,第 $i$ 个字符确定第 $i$ 项的系数,令 R,S,P 分别对应 $a_i=1,\omega,\omega^2$ ,
对 $B$ 构造一个多项式 $B(x)$, 第 $i$ 个字符确定第 $i$ 项的系数,令 R,S,P 分别对应 $b_i=1,\omega^2,\omega$ .
其中 $\omega$ 为 $3$ 次单位根.
在某个循环移位下,比赛对应的两个字符在原串中下标之差在模 $k$ 意义下是确定的,即 $(i-j)\bmod k$ 为定值.
于是我们将 $A(x),B^R(x)$ 这两个多项式做循环卷积,若胜负场数都一样,则得到的多项式每一项的系数是相同的.
循环卷积可以用 DFT 来计算,乘出来的多项式为 ${\rm IDFT}({\rm DFT}(A) \cdot {\rm DFT}(B^R))$ ,点乘为各项系数对应相乘.
考虑 IDFT 的本质是代入了 $k$ 个点值,将得到的每个值作为系数,而我们要求每个系数相同,说明我们代入点值的 $k-1$ 次多项式,即 ${\rm DFT}(A) \cdot {\rm DFT}(B^R)$ 应当是一个常数函数,即除了常数项外,其余系数都是 $0$ .忽略常数项,就等价于要求 ${\rm DFT}(A),{\rm DFT}(B)$ 不能存在某一项的系数同时不为 $0$ ,将非 $0$ 的视作 $1$ ,可以看成二进制数按位与为 $0$ .
$A,B$ 的构造形式不一样,不便于我们统计答案,但由于我们此时只考虑系数是否为 $0$ ,所以可以对 $B^R(x)$ 大胆操作:
$$
{\rm DFT}(B^R(x))=\sum_{j=0}^{k-1}x^j\cdot \sum_{i=0}^{k-1}b_{k-i-1}\omega_k^{ij}\\
{\rm DFT}(B^R(x))=\sum_{j=0}^{k-1}x^j\cdot \omega_{k}^{k-j}\cdot\sum_{i=0}^{k-1}(\frac 1 {b_{k-i-1}}\omega_k^{(k-i)j})^{-1}\\
{\rm DFT}(B^R(x))=\sum_{j=0}^{k-1}x^j\cdot \omega_{k}^{k-j}\cdot\sum_{i=0}^{k-1}(a_i\omega_k^{ij})^{-1}\\
{\rm DFT}(B^R(x))=\sum_{j=0}^{k-1}x^j\cdot \omega_{k}^{k-j}\cdot\sum_{i=0}^{k-1}\overline {a_i\omega_k^{ij}}
$$
变式的依据是单位根的任意次幂模长都为 $1$ ,此时它的共轭和倒数是相等的.
这意味着在构造 $B(x)$ 时,也同样使用 $a_i$ 作为系数,也不用反转,直接 DFT, 不会影响系数是否为 $0$ ,形式就统一了.
用 Bluestein 暴力求出每个人的 ${\rm DFT}(A)$ ,去掉常数项后,将非 $0$ 的系数用 $1$ 替换,得到一个二进制数 $x_i$ ,则答案转化为,从 $n$ 个人中选出一个非空子集,满足子集中所有的 $x_i$ 两两按为与都为 $0$ ,即交集为空,求合法方案数.
接下来就是个状压 dp 了,记 $cnt(x)$ 表示满足 $x_i=x$ 的 $i$ 的数目,记 $dp(S)$ 表示选择的 $x_i$ 并集为 $S$ 的合法方案数,转移时枚举一个 $S\cap T=\emptyset$ 的 $T$ ,表示加入一个 $x_i=T$ 的数,将 $dp(S)\cdot cnt(T)$ 加到 $dp(S\cup T)$ 中即可.
时间复杂度 $O(nk^2+3^k)$ ,用 Bluestein 求每个人的 ${\rm DFT}(A)$ 可以做到 $O(nk\log k+3^k)$ ,但应该打不过暴力.
感觉 Topcoder 的题提交比较麻烦,代码就先鸽了,反正看上去应该不难实现.