单位根反演

给定$n,k$, 求$sum inom{n}{km}$, 时间复杂度$O(klog n)$

下指标求和, 考虑函数$(1+x)^n$在单位根处的值, 有

$$
egin{bmatrix}
1 & 1 & cdots & 1 \
1 & omega^1 & cdots & omega^{k-1} \
vdots & vdots & ddots & vdots \
1 & omega^{k-1} & cdots & omega^{(k-1)(k-1)}
\
end{bmatrix}
egin{bmatrix}
f_0\f_1\vdots\f_{k-1}
end{bmatrix}=
egin{bmatrix}
2^n\(1+omega)^n\vdots\(1+omega^{k-1})^n
end{bmatrix}
$$

其中$f_i=sum inom{n}{km+i}$, $omega$为$k$次单位根

所以可以得到

$$f_i=frac{1}{k}sumlimits_{j=0}^{k-1}omega^{-ij}(1+omega^j)^n$$

所以$f_0=frac{1}{k}sumlimits_{j=0}^{k-1} (1+omega^j)^n$

对于函数$A(x)=sum limits_{i=0}^{n-1} a_i x^i$

利用同样的方法可以得到$sum a_{mk+i}= frac{1}{k}sumlimits_{j=0}^{k-1}omega^{-ij} A(omega^j)$