核心式子
\[[k|n]=\dfrac 1k\sum_{i=0}^{k-1} \omega_k ^{i\cdot n} \]证明：
-
当 \(n\) 是 \(k\) 的因数时，\(\dfrac 1k\sum\limits_{i=0}^{k-1} \omega_k ^{i\cdot n}=\dfrac 1k\sum\limits_{i=0}^{k-1} \omega_k^0 =\dfrac 1k\cdot k=1\)
-
当 \(n\) 不是 \(k\) 的因数时，\(\dfrac 1k\sum\limits_{i=0}^{k-1} \omega_k ^{i\cdot n}= \dfrac 1k\cdot \dfrac{\omega_k^{kn} -1}{\omega_k^n -1}=\dfrac 1k\cdot \dfrac{1 -1}{\omega_k -1} =0\)
然后我们知道 \(w_n ^k \equiv a^{\frac{p-1}n\cdot k} \pmod p\) 就可以求了，其中 \(a\) 是 \(p\) 的原根。
例题
题意：多测，给出 \(n,s,a_0,a_1,a_2,a_3\)，求
\[(\sum\limits_{i=0}^n {n \choose i}\cdot s^i\cdot a_{i\bmod 4}) \bmod 998244353 \]\(1\le T\le 10^5,\space 1\le n\le 10^{18},\space 1\le s,a_0,a_1,a_2,a_3\le 10^8\)
推式子
\[\begin{aligned} \text{原式} &= \sum_{r=0}^3 a_r\sum_{i=0} ^n [i\bmod 4=r]{n \choose i} \cdot s^i \\ &= \sum_{r=0} ^3 a_r\sum_{i=0} ^n [4|(i-r)] {n\choose i} \cdot s^i\\ &= \sum_{r=0} ^3 a_r\sum_{i=0} ^n \frac 14 \sum_{j=0} ^3 \omega_4 ^{(i-r)j} {n\choose i} \cdot s^i\\ &= \frac 14\sum_{r=0} ^3 a_r\sum_{i=0} ^n \sum_{j=0}^3 \omega_4^{ij} \cdot \omega_4^{-rj} {n\choose i} \cdot s^i \\ &= \frac 14\sum_{r=0} ^3 a_r\sum_{j=0} ^3 \omega_4^{-rj} \sum_{i=0} ^n (\omega_4^j)^i \cdot s^i {n\choose i} \\ &= \frac 14\sum_{r=0} ^3 a_r\sum_{j=0} ^3 \omega_4^{-rj} (\omega_4^j \cdot s +1)^n \end{aligned} \]直接做，快速幂，\(O(T\log p)\)。 记录
题意：给出 \(n,p,k\)，求
\[\sum_{i=0}^n {n \choose i}\cdot p^i\cdot \lfloor \frac ik\rfloor \pmod {998244353} \]\(1\le n,p\le 998244353,\space k\in \{2^w| 0\le w\le 20\}\)
把 \(\lfloor\dfrac ik\rfloor\) 拆成 \(i\) 和 \(i\bmod k\) 两部分，最后再除以 \(k\)。
\[\begin{aligned} \text{第一部分式子} &= \sum_{i=0}^n {n\choose i} \cdot p^i \cdot i \\ &= \sum_{i=1}^n {n-1 \choose i-1} \cdot p^i \cdot n \\ &= np \sum_{i=0}^{n-1} {n-1\choose i} p^i \\ &= np(p+1)^{n-1} \\ \\ \text{第二部分式子} &= \sum_{i=0}^n {n\choose i} \cdot p^i \cdot (i\bmod k) \\ &= \sum_{r=0}^{k-1} r\sum_{i=0}^n [i\bmod k=r] {n\choose i} \cdot p^i \\ &= \sum_{r=0}^{k-1} r\sum_{i=0}^n [k|(i-r)] {n\choose i} \cdot p^i \\ &= \sum_{r=0}^{k-1} r \sum_{i=0}^n \sum_{j=0} ^{k-1} \omega_k^{(i-r)j} {n\choose i}\cdot p^i \\ &= \sum_{r=0}^{k-1} r \sum_{i=0}^n \sum_{j=0} ^{k-1} \omega_k^{ij}\cdot \omega_k^{-rj} {n\choose i}\cdot p^i \\ &= \sum_{r=0}^{k-1} r \sum_{j=0} ^{k-1} \omega_k^{-rj} \sum_{i=0}^n (\omega_k^j)^i \cdot {n\choose i} \cdot p^i \\ &= \sum_{r=0}^{k-1} r \sum_{j=0} ^{k-1} \omega_k^{-rj} (\omega_k^j \cdot p+1)^n\\ &= \sum_{j=0} ^{k-1} (\omega_k^j \cdot p+1)^n \sum_{r=0}^{k-1} r\cdot \omega_k^{-rj}\\ \end{aligned} \]注意右边枚举 \(r\) 的式子，不妨设为 \(S(k,\omega_k^{-j})\)，有
\[S(n,k)=\sum_{i=0}^{n-1} i\cdot k^i \]则
\[\begin{aligned} k\cdot S(n-k)-S(n,k) &= \sum_{i=1}^n (i-1)k^i - \sum_{i=0}^{n-1}i\cdot k^i \\ &= -\sum_{i=1}^{n-1} k^i +(n-1)k^n \\ &= -\frac{k^n-k}{k-1} +(n-1)k^n \end{aligned} \]注意到每次带入的 \(S(n,k)\) 中 \(k\) 总是 \(n\) 的单位根的幂，有 \(k^n=1\)，则
\[\begin{aligned} -\frac{k^n-k}{k-1} +(n-1)k^n &= -\frac{1-k}{k-1}+(n-1) \\ &= 1+(n-1) \\ &= n \end{aligned} \]因此 \(S(n,k)=\dfrac n{k-1}\)。
特别的，当 \(k=1\) 时，\(S(n,1)=\sum_{i=0}^{n-1} i = \dfrac{n(n-1)}2\)。
直接求，\(O(k\log p)\)。记录
标签：le,cdot,dfrac,sum,单位根,反演,choose,omega,小记 From： https://www.cnblogs.com/Sktn0089/p/18051511