最好的占位多项式

· · 个人记录

来复习一下占位多项式，参考 Elegia. Hello, multivariate multiplication. 一文，我们可以给出占位多项式的定义，也就是在混合基表示下

i = i_1 + i_2N_1 + i_2N_1N_2 + \cdots + i_{d}N_1\cdots N_{d-1}

然后 \chi(i) + \chi(j) \equiv \chi(i + j) \pmod{d} 当且仅当 i 和 j 在混合基下相加不产生“进位”，实际上，这样的占位多项式是不一定是唯一的，但是 Elegia 给出的占位多项式是最好的。

注意这里的 i 和 j 不产生进位指的是在 i + j \lt \prod_{k=1}^{d}N_k 时，否则我们不管是否产生进位（其实是一定产生进位），溢出的直接丢掉。

我们最好说的其实是对于缓存而言应该是最友好的。

占位多项式实际上是决定了“贡献”的位置，也就是说，如果我们将整个多项式进行“分类”，然后让那些 i + j 产生进位的 i 和 j 贡献到无关的位置即可。

这时候考虑块和块之间的间隔（更大块和更大块之间的间隔等等），通过调整这些应该可以拿到所有可能的占位多项式，但是就缓存友好而言，不难发现还是 Elegia 给出的是最优的。

在二维卷积（次数在片段中）中，有下面两种合法的 \chi 函数。

dim = 2
[2, 3]
All valid chi function(s): 
[0, 0, 1, 1, 0, 0]
[0, 1, 1, 0, 0, 1] // 块长度为 2，也就是 [0, 1] [1, 0] [0, 1]

Elegia's chi function: 
[0, 0, 1, 1, 0, 0]

我们可以用两个数组分别描述“间隔”，第一个是 [0, 1]，第二个是 [1, 1]。

下面是三维卷积（次数在片段中）中所有合法的 \chi 函数，可以发现第一个就是 Elegia 给出的，而第二个调整了块和块的间隔，第三个相邻的间隔为 1，等等。

dim = 3
[4, 2, 3]
All valid chi function(s): 
[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 2, 2, 2, 2, 0, 0, 0, 0, 2, 2, 2, 2, 0, 0, 0, 0, 2, 2, 2, 2]
[0, 1, 2, 0, 0, 1, 2, 0, 2, 0, 1, 2, 2, 0, 1, 2, 1, 2, 0, 1, 1, 2, 0, 1]
[0, 1, 2, 0, 2, 0, 1, 2, 2, 0, 1, 2, 1, 2, 0, 1, 1, 2, 0, 1, 0, 1, 2, 0]
[0, 2, 1, 0, 0, 2, 1, 0, 1, 0, 2, 1, 1, 0, 2, 1, 2, 1, 0, 2, 2, 1, 0, 2]
[0, 2, 1, 0, 1, 0, 2, 1, 1, 0, 2, 1, 2, 1, 0, 2, 2, 1, 0, 2, 0, 2, 1, 0]

Elegia's chi function: 
[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]

我们可以用数组描述“间隔”，分别是

[0, 1, 0]
[0, 2, 0]
[1, 0, 2]
[1, 2, 2]
[2, 0, 1]
[2, 1, 1]

以最后一行为例，详细说明一下 [2, 1, 1] 是什么意思，在第一维是四个，我们将整个数组划分为

[0, 2, 1, 0] 0 (+2) -> 2 (+2) -> 1 (+2) -> 0
[1, 0, 2, 1] ...
[1, 0, 2, 1] ...
[2, 1, 0, 2] ...
[2, 1, 0, 2] ...
[0, 2, 1, 0] ...

每一块中间隔都是 2，所以第一个数字是 2，考虑第二个 1 的意思是

[0, 2, 1, 0] 每个 +1 -> [1, 0, 2, 1]
[1, 0, 2, 1] 每个 +1 -> [2, 1, 0, 2]
[2, 1, 0, 2] 每个 +1 -> [0, 2, 1, 0]

剩下一个 1 的意思是

[0, 2, 1, 0, 1, 0, 2, 1] 每个 +1 -> [1, 0, 2, 1, 2, 1, 0, 2] ...

在同一个合法的 \chi 函数上，这个“间隔”数组都是适用的，其实也容易想象。如果要构造这样一个间隔数组，根据等差数列的特性，我们应该只需要检查若干个位置是否符合性质就行了。而因为 0 这个位置很特殊，是固定的，所以可能比较容易构造（但是真的有必要用其他的占位函数吗，除非它能够让我们避免使用二倍长度的 FFT，但是我还没有想到如何构造出这样的）

如此我们便可以快速计算占位函数 \chi，借助“间隔”数组，我们可以递推出所有的占位函数而不是全部根据定义计算。

根据一些简单的测试 https://www.luogu.com.cn/paste/2pksgh4c，发现很难避免二倍长度的 FFT，除非将 d 提升到原先的二倍加一（如果这样的话，计算量其实还增加了？）当然没有什么严谨的证明。好像从侧面说明了，如果只做一次 FFT 想要多次卷积的话是很难行得通的，和之前子集卷积是不同的处理手法，毕竟子集卷积我们按照次数分类成多个齐次多项式时后续卷积已经没有去做那些显然会溢出的了，而 FFT 会溢出是没办法避免的，除非我们仍然按照次数分类。