「学习笔记」浅谈自相关多项式
貌似用处并不是很大的科技，可能可以解释一些题目的做法。
一些定义
定义一个长度为 \(n\) 的字符串 \(S\) 的自相关多项式 (autocorrelation polynomial) \(c(x)=\sum\limits_{i=0}^{n-1}[i\ \text{is a period of}\ S]x^i\)，其中 \(i\) 是 \(S\) 的 period 当且仅当 \(\forall 0\le j\lt n-i\) 满足 \(S_j=S_{j+i}\)
设字符集大小为 \(m\)，设 \(f_i\) 表示长度为 \(i\) 的所有字符串，正好在末尾出现第一次匹配串的方案数，\(F(x)\) 为它的 OGF，\(g_i\) 表示长度为 \(i\) 的所有字符串，还没出现匹配串的方案数，\(G(x)\) 为它的 OGF，\(h_i\) 表示长度为 \(i\) 的所有字符串，至少出现过一次匹配串的方案数，\(H(x)\) 为它的 OGF
一些公式推导
\[G(x)\cdot mx+1=F(x)+G(x)\tag{1}\]
\((1)\) 式的含义是，将任意一个未出现匹配串的字符串后加入任意字符，要么恰好出现第一次，要么还没有出现，\(1\) 是补齐常数项
\[G(x)\cdot x^n=F(x)\cdot c(x)\tag{2}\]
\((2)\) 式的含义是，将任意一个未出现的字符串后直接加入匹配串，注意到它不一定是第一次出现，有可能加入了 \(i\) 个字符后他就恰好在末尾第一次出现匹配串了，后面又钦定加入了剩余的 \(n-i\) 位，注意到此时 \(i\) 一定是匹配串的 border 即 \(n-i\) 是匹配串的 period 那么此时的贡献正好为 \(i\) 位后的 \(f\) 值乘上 \(n-i\) 位的固定串
将 \((1)\) 式变形为 \(G(x)=\frac{F(x)-1}{mx-1}\) 带入 \((2)\) 式，可得 \(F(x)=\frac{x^n}{x^n+(1-mx)c(x)},G(x)=\frac{c(x)}{x^n+(1-mx)c(x)}\)
考虑求 \(H(x)\) 注意到对于任意刚好在末尾出现一次的字符串 \(F(x)\) 在其末尾继续加入任意串，可拓展为至少出现一次匹配串的方案数，注意到 \(F(x)\) 所代表的串是不重的，不难证明这样可以不重不漏地拓展到所有串，于是有 \(H(x)=\sum\limits_{i=0}^\infty F(x)\cdot(mx)^i=\frac{x^n}{(1-mx)(x^n+(1-mx)c(x))}\)
好像这就是歌唱王国？