专栏文章

最好的占位多项式

hhly1204
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqk2b2z
此快照首次捕获于
2025/12/04 06:05
3 个月前
此快照最后确认于
2025/12/04 06:05
3 个月前
查看原文
来复习一下占位多项式，参考 Elegia. Hello, multivariate multiplication. 一文，我们可以给出占位多项式的定义，也就是在混合基表示下
i=i1+i2N1+i2N1N2+⋯+idN1⋯Nd−1i = i_1 + i_2N_1 + i_2N_1N_2 + \cdots + i_{d}N_1\cdots N_{d-1}
然后 χ(i)+χ(j)≡χ(i+j)(modd)\chi(i) + \chi(j) \equiv \chi(i + j) \pmod{d} 当且仅当 ii 和 jj 在混合基下相加不产生“进位”，实际上，这样的占位多项式是不一定是唯一的，但是 Elegia 给出的占位多项式是最好的。
注意这里的 ii 和 jj 不产生进位指的是在 i+j<∏k=1dNki + j \lt \prod_{k=1}^{d}N_k 时，否则我们不管是否产生进位（其实是一定产生进位），溢出的直接丢掉。
我们最好说的其实是对于缓存而言应该是最友好的。
占位多项式实际上是决定了“贡献”的位置，也就是说，如果我们将整个多项式进行“分类”，然后让那些 i+ji + j 产生进位的 ii 和 jj 贡献到无关的位置即可。
这时候考虑块和块之间的间隔（更大块和更大块之间的间隔等等），通过调整这些应该可以拿到所有可能的占位多项式，但是就缓存友好而言，不难发现还是 Elegia 给出的是最优的。
在二维卷积（次数在片段中）中，有下面两种合法的 χ\chi 函数。
TEXT
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 给出的，而第二个调整了块和块的间隔，第三个相邻的间隔为 11，等等。
TEXT
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]
我们可以用数组描述“间隔”，分别是
TEXT
[0, 1, 0]
[0, 2, 0]
[1, 0, 2]
[1, 2, 2]
[2, 0, 1]
[2, 1, 1]
以最后一行为例，详细说明一下 [2, 1, 1] 是什么意思，在第一维是四个，我们将整个数组划分为
TEXT
[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 的意思是
TEXT
[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 的意思是
TEXT
[0, 2, 1, 0, 1, 0, 2, 1] 每个 +1 -> [1, 0, 2, 1, 2, 1, 0, 2] ...
在同一个合法的 χ\chi 函数上，这个“间隔”数组都是适用的，其实也容易想象。如果要构造这样一个间隔数组，根据等差数列的特性，我们应该只需要检查若干个位置是否符合性质就行了。而因为 00 这个位置很特殊，是固定的，所以可能比较容易构造（但是真的有必要用其他的占位函数吗，除非它能够让我们避免使用二倍长度的 FFT，但是我还没有想到如何构造出这样的）
如此我们便可以快速计算占位函数 χ\chi，借助“间隔”数组，我们可以递推出所有的占位函数而不是全部根据定义计算。
根据一些简单的测试 https://www.luogu.com.cn/paste/2pksgh4c，发现很难避免二倍长度的 FFT，除非将 dd 提升到原先的二倍加一（如果这样的话，计算量其实还增加了？）当然没有什么严谨的证明。好像从侧面说明了，如果只做一次 FFT 想要多次卷积的话是很难行得通的，和之前子集卷积是不同的处理手法，毕竟子集卷积我们按照次数分类成多个齐次多项式时后续卷积已经没有去做那些显然会溢出的了，而 FFT 会溢出是没办法避免的，除非我们仍然按照次数分类。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...