單位根反演推導(dǎo)

請大家注意：

因為作者寫的文章中的梯等式公式總是莫名的顯示錯誤，所以作者的許多文章中的梯等式都暴力拆成一步一個等式了。
造成的不適，請諒解。
同時，如果文章中還有其他錯誤，請聯(lián)系作者，謝謝。

問題模型

給出兩個整數(shù)N,S以及一個長度為4的數(shù)組A_{0 \sim 3}。
求：\sum_{i=0}^{n} C(n,i) S^i A_{(i \mod 4)}。

公式推導(dǎo)

因為只有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}
考慮證明：

  1. k|n成立，那么顯然等于1。
  2. 如果k\not|n，那么可以寫成等比數(shù)列求和：\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
就做完了。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 請大家注意： 因為作者寫的文章中的梯等式公式總是莫名的顯示錯誤，所以作者的許多文章中的梯等式都暴力拆成一步一個等式...
    Tacmon_old閱讀 931評論 0贊 0
  • 昨天，媽媽帶我去拔牙，因為我很勇敢，所以，媽媽獎勵我了一盒熒光筆，我非常高興，里面一共有6只熒光筆，有粉色...
    楊雨馨閱讀 343評論 0贊 0
  • 捷后愚生閱讀 152評論 1贊 2
  • 無所謂短暫永恒 無所謂你們下什么定義 我只知道春天來了 我要開花
    那時花開MRR閱讀 251評論 0贊 0

友情鏈接更多精彩內(nèi)容