今天用多项式的角度重新审视 [六省联考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(·)\)