「算法學習」單位根反演

第一次試試用國語寫博客，感覺整個博客上流起來了

引子

• Question -1：

  求 $\sum_{i=0}^{n}a_i$

  四肢健全的人都會做吧😅

• Question 0：

  求 $\sum_{i=0}^{n}a^{i}[2|i]$

  對著這個式子看一看，熟練的人就想到了 ${-1}^i$ 在 $i$ 奇偶性改變的時候回表現出兩種不同的形態，我們可以利用這個性質，求出 $f(x) = \sum_{i=0}^na_ix^i$ 這個多項式在 -1 和 1 處的取值，然後簡單容斥就可以計算出這個式子的值了。

• Question 1：

  求 $\sum_{i=0}^n a_i[k|i]$ ， $3 \le k \le 10$

  這個東西看起來只能暴力算，除非我們可以按照之前 Q0 的做法來搞出一個類似的數 $w$，使得 $w^x$ 在 $x \bmod k$ 的餘數相同的時候值一致，否則值不一致，並且不同的值之間還有一些比較簡單的關係，這樣我們也可以用上邊的簡單容斥來計算這個東西了，這時我們就想到了有這麼一個東西他滿足這個性質。

算法描述

剛剛我們說可以滿足這個性質的數就是 $\omega_k$ ，也就是 k 次單位根。

但是知道這個還不夠，我們想要知道如何用單位根湊出 $[i|k]$ 。

於是這個時候就要請出我們的單位根反演了：

$$[k|n] = \frac1k\sum_{i=0}^{k-1}\omega_{k}^{ni}$$

證明

讓我們了解一下這個式子的本質是什麼。

因為 $\omega_k^k=1$ ，所以我們可以構造一個等比數列，其中末項乘公比為 $\omega_k^{ak}$ ，首項為 $\omega_k^0$ ，這樣如果公比不為 0 的話，這個式子求出來就是 0（套用等比數列求和公式），否則的話我們如果直接套用公式那麼分子就是 0 ，式子本身沒有意義。但是公比為 1 也就意味著每一個數都一樣，既然首項為 $\omega_k^0$，那麼每一項也就是 $\omega_k^0 = 1$ 。而 $\omega_k^n$ 只有在 $[k|n] = 1$ 的時候才為 1 ，所以上面那個式子在 $[k|n]=1$ 的時候值為 1，否則值為 0。

拓展應用

這個式子遠遠沒有那麼簡單。我們可以把它套入到別的其他很多東西中，因為是要這個等比數列還在，這個式子就是滿足的。所以回到上面的 Question1，我們要求出 $\sum_{i=0}^{n}a_i[k|i]$ ，我們可以直接求出 $\frac1k\sum_{i=0}^{k-1}f(\omega_k^i)$ ，這樣對於每個 $x^i$ 的貢獻就也是一個等比數列了，本質上就回到了上面的單位根反演。

相關的應用還有：zr1804 21省選10聯測day9T2