单位根反演小记

显然我还不会这个，但是我先写点，写到啥算啥。

单位根反演的式子。

\([n|a]=\frac {1} n\sum\limits_{k=0}^{n-1} \omega ^{ak}_n\)

证明：

• $a\not = 0 $ 时，\(=\frac 1 n\sum\limits_{k=0}^{n-1} \omega_{n}^{ak}\)

  \(=\frac 1 n \frac {1-\omega^{an}}{1-\omega^a}\)。因为 $\omega^{a}\not =1 $ 并且 \(\omega ^n =1\)， 所以原式等于 \(0\)。

• \(a=0\) 时，\(=\frac 1 n\sum\limits _{k=0}^{n-1} \omega^{0}=1\)。

就这个式子，很可爱。

#loj6485. LJJ 学二项式定理

题意：求 \(\displaystyle[\sum _{i=0}^n \dbinom{n}{i}s^ia_{(i\mod 4)}]\mod 998244353\)

\(T\leq 10^5,n\leq 10^{18}\)。

注意是 \(i\mod 4\)。

首先把式子化成： \(\displaystyle \sum_{i=0}^{n} \dbinom{n}{i} s^i \sum_{j=0}^3 a_{j} [i\mod 4==j]\)

\(\displaystyle \sum_{i=0}^{n} \dbinom{n}{i} s^i \sum_{j=0}^3 a_j \sum_{k=0}^{3} \omega_{4}^{(i-j)k}\)

\(\displaystyle \sum_{k=0}^3\sum _{j=0}^3 a_j \omega_{4}^{-jk} \sum_{i=0}^{n}\dbinom{n}{i} s^i\omega_4^{ik}\)

二项式定理。

\(\displaystyle \sum_{k=0}^{3}\sum_{j=0}^{3} a_j \omega_{4}^{-jk} (1+s\omega^k)^n\)。

完事了，单位根就是 \(g^\frac {mod-1} 4\)

困了，不想写了，睡了。

奔驰在国道上时速七十公里

追寻着幻影不知道幸福在哪

开窗丢掉所有过往犹豫彷徨

从此我不是我是新的我对自己说

嘿

无所谓了跳起来吧 wowowo

想什么呢等什么呢 wowowo

跳起来吧无所谓了 wowowo

wowowo

嘿

无所谓了跳起来吧 wowowo

想什么呢等什么呢 wowowo

跳起来吧无所谓了 wowowo

wowowo