单位根反演推导

作者: Tacmon_old | 来源:发表于2020-01-12 12:49 被阅读0次

请大家注意：

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

问题模型

给出两个整数 $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$
就做完了。

网友评论

本文标题：单位根反演推导

本文链接：https://www.haomeiwen.com/subject/lxiiactx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！