单位根反演推导

请大家注意：

因为作者写的文章中的梯等式公式总是莫名的显示错误，所以作者的许多文章中的梯等式都暴力拆成一步一个等式了。
造成的不适，请谅解。
同时，如果文章中还有其他错误，请联系作者，谢谢。

问题模型

给出两个整数 $N,S$ 以及一个长度为 $4$ 的数组 $A_{0 \sim 3}$ 。
求： $\sum_{i=0}^{n} C(n,i) S^i A_{(i \mod 4)}$ 。

公式推导

因为只有 $4$ 个值，所以我们考虑将答案拆开：
$Ans = \sum_{r=0}^{3} \sum_{i=0}^{n} [i \equiv r\mod 4] C(n,i) S^i$
我们考虑单位根反演：
$[k|n] = \frac{1}{k} \sum_{i=0}^{k-1} \omega_{k}^{in}$
考虑证明：

$k|n$ 成立，那么显然等于 $1$ 。
如果 $k\not|n$ ，那么可以写成等比数列求和： $\sum_{i=0}^{k-1}\omega_{k}^{in} = \frac{\omega_{k}^{kn}-1}{\omega_{k}^{n}-1} = 0$

那么我们就可以将答案写成：
$Ans = \sum_{r=0}^{3} A_r \sum_{i=0}^{n} [4 | (i-r)] C(n,i) S^i$
$Ans = \sum_{r=0}^{3} A_r \sum_{i=0}^{n} C(n,i) S^i \frac{1}{4} \sum_{j=0}^{3}\omega_{4}^{(i-r)j}$
$Ans = \sum_{r=0}^{3} A_r \sum_{j=0}^{3} \omega_{4}^{-jr} \sum_{i=0}^{n} C_{n}^{i} S^i \omega_{4}^{ij}$
$Ans = \sum_{r=0}^{3} A_r \sum_{j=0}^{3} \omega_{4}^{-jr} (S\omega_{4}^{j}+1)^n$
就做完了。

最后编辑于：2020.03.25 19:35:28

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

单位根反演推导