單位根反演

$[k\mid n]=\frac{1}{k}{\sum }_{i=0}^{k?1}{\omega }_k^{in}$

$k$ 次單位根是 $k$ 次冪為 $1$ 的復(fù)數(shù)解 $w_k$。利用單位圓和單位根的關(guān)系很容易證明。

• $k\mid n$

  顯然 ${\omega }_k^{in}$，相當(dāng)于轉(zhuǎn)了 $\frac{in}{k}$ 圈單位圓，結(jié)果仍是 $1$。

  $\frac{1}{k}{\sum }_{i=0}^{k?1}1=1=k\mid n$

• $k?n$

  使用等比數(shù)列求和。

  $[k\mid n]=\frac{1}{k}{\sum }_{i=0}^{k?1}{\omega }_k^{in}=\frac{1}{k}?\frac{{\omega }_k^{nk}?1}{{\omega }_k^n?1}$

  $\because {\omega }_k^{nk}?1={\omega }_k^0?1=0\wedge {\omega }_k^n?1=0$

  $\therefore \frac{1}{k}{\sum }_{i=0}^{k?1}{\omega }_k^{in}=0=[k\mid n]=k?n$

LOJ6485. LJJ學(xué)二項(xiàng)式定理

$T$ 組數(shù)據(jù)，給定 $n,s,a_0,a_1,a_2,a_3$，求 ${\sum }_{i=0}^{n}C(n,i)?s^i?a_{i(\mathrm{m}\mathrm{o}\mathrm{d}4)}$。結(jié)果對(duì) $998244353$ 取模。

趁熱打鐵，我們很容易想到將 $i$ 按模 $4$ 的余數(shù)進(jìn)行分類。對(duì)于每一類我們只想統(tǒng)計(jì)該統(tǒng)計(jì)的數(shù)。
$$\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)s^i\sum _{j=0}^3{a}_j[i\text{mod}4=j]=\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)s^i\sum _{j=0}^3{a}_j[4\mid (i?j)]$$
直接單位根反演：$[4|(i?j)]=\frac{1}{4}{\sum }_{k=0}^3{\omega }_4^{k(i?j)}$
$$?\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)s^i?\frac{1}{4}\sum _{j=0}^3{a}_j?\sum _{k=0}^3{\omega }_4^{ki}{\omega }_4^{?kj}=\frac{1}{4}\sum _{j=0}^3{a}_j\sum _{k=0}^3{\omega }_4^{?kj}\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)s^i{\omega }_4^{ki}$$
二項(xiàng)式定理：${\sum }_{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)s^i{\omega }_4^{ki}={\sum }_{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)(s{\omega }_4^k{)}^i=(s{\omega }_4^k+1{)}^n$
$$?\frac{1}{4}\sum _{j=0}^3{a}_j\sum _{k=0}^3{\omega }_4^{?jk}(s{\omega }_4^k+1{)}^n$$
模 $998244353$ 意義下是有四次單位根的，且原根為 $3$，有 ${\omega }_4^1=g^{(mod?1)/4}$。

直接算即可。

#include <bits/stdc++.h> using namespace std; #define int long long #define mod 998244353 int T, n, s; int a[10], w[10] = { 1, 911660635, 998244352, 86583718 };int qkpow( int x, int y ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; }signed main() {scanf( "%lld", &T );while( T -- ) {scanf( "%lld %lld", &n, &s );for( int i = 0;i < 4;i ++ ) scanf( "%lld", &a[i] );int ans = 0;for( int i = 0;i < 4;i ++ ) {int sum = 0;for( int j = 0;j < 4;j ++ )( sum += w[(4 - i) * j % 4] * qkpow( s * w[j] % mod + 1, n ) ) %= mod;( ans += sum * a[i] ) %= mod;}printf( "%lld\n", ans * qkpow( 4, mod - 2 ) % mod );}return 0; } /* 6 1 2 3 4 5 6 2 3 4 5 6 1 3 4 5 6 1 2 4 5 6 1 2 3 5 6 1 2 3 4 6 1 2 3 4 5 */ 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[学习笔记] 单位根反演的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。