0%

循环、模、单位根的思考

今天用多项式的角度重新审视 [六省联考2017]组合数问题 这道题。

题干要求

\[ \sum_{i\bmod k=r}\dbinom{nk}{i} \]

的值。 前年做这一道题是直接看了题解,通过找与之等价的组合意义完成的,现在让我们重新做一遍。

很容易化简得到

\[ \sum_{i\bmod k=r}\lbrack x^i\rbrack(1+x)^{nk} \]

现在看来这个式子意义十分显然,即 \((1+x)^{nk}\)\(k\) 循环卷积即可。关于循环卷积运算,一直以来有对其正确性的疑问,但现在似乎是搞明白了。

假设 \(D_k\) 是对多项式进行约化的算子,即

\[ D_k(f)=\sum_i([x^i]f)x^{i\bmod k} \]

\(\circ\) 表示循环卷积的算符,很容易验证其对 \(+\) 有分配律。

下面讨论命题

\[ D_k(f\times g)=D_k(f)\circ D_k(g) \]

的正确性。

我们对左式展开

\[ \begin{aligned} D_k(f\times g)&=\sum_i([x^i](f\times g))x^{i\bmod k}\\\\ &=\sum_a\sum_b([x^a]f\times[x^b]g)x^{a+b\bmod k}\\\\ &=\sum_a ([x^a]f)x^{a\bmod k}\circ \sum_{b}([x^b]f)x^{b\bmod k}\\\\ &=D_k(f)\circ D_k(g) \end{aligned} \]

而今天看到 \(\mathrm{jiangly}\)\(D_k\) 有另外的表述即

\[ D_k(f)=f\bmod x^k-1 \]

这是我第一次见到这样的表述,题解没有细说,它的正确性我口胡了一个证明。

容易验证多项式模运算与整数模运算性质类似,我们不妨考虑 \(x^n\bmod x^k-1\) 的值,显然有

\[ x^n=(\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}x^{n-ik})(x^k-1)+x^{n\bmod k} \]

\(x^n\equiv x^{n\bmod k}\bmod x^k-1\)

所以对最开始命题的正确性可以用 \(\bmod x^k-1\) 相关运算的性质来说明。

另外,在看到这道题时,还有一个思路就是单位根反演,即

\[ [n|k]=\dfrac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ik} \]

我们将此式联系题目,即

\[ \begin{aligned} \mathbf{Ans}&=\sum_{r=0}^{k-1}\sum_{i}[k|i-r]\lbrack x^i\rbrack(1+x)^{nk}\\\\ &=\dfrac{1}{k}\sum_{r=0}^{k-1}\sum_{i}\sum_{j=0}^{k-1}\omega_k^{(i-r)j}\lbrack x^i\rbrack(1+x)^{nk}\\\\ &=\dfrac{1}{k}\sum_{r=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-rj}\sum_{i}\omega_k^{ij}\lbrack x^i\rbrack(1+x)^{nk}\\\\ &=\dfrac{1}{k}\sum_{r=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-rj}(1+\omega_k^j)^{nk}\\\\ &=\mathbf{IDFT}_k[\mathbf{DFT}_k[(1+x)^{nk}]] \end{aligned} \]

换句话说 \(\mathbf{IDFT}_k[\mathbf{DFT}_k[·]]=D_k(·)\)