前言

之前寫反演的博客對于單位根反演只提了FFT
這里補一下一個應用

單位根反演

$$f_i=\sum _{j=0}^{n?1}{\omega }_n^{i?j}{g}_j?g_i=\sum _{j=0}^{n?1}\frac{{\omega }_n^{?i?j}}{n}{f}_j$$
這是FFT里的
證明很方便，見我的博客對于容斥原理&反演的思考和總結
事實上，我們思考上式的本質
我們發現就是
$$[n|x]=\frac{1}{n}\sum _{i=0}^{n?1}({\omega }_n^x{)}^i$$
FFT中的形式把$x$取值$a?b$，又保證$|a?b|<n$那么$n|x$只有在$a=b$的時候滿足，即${\delta }_{a,b}$
所以根據這個我們可以得到更多的應用，常見形式如下
對一個多項式
$$f(x)=\sum _{i=0}^{n?1}{a}_i{x}^i$$
求所有次數為$k$的倍數的系數之和
$$\begin{array}{rl}Ans& =\sum _{i=0}^{n?1}[k|i]a_i\end{array}$$

題解

題目要求的是
$$\left[\sum _{i=0}^n\left(\left(\genfrac{}{}{0ex}{}{n}{i}\right)?s^i?a_{imod4}\right)\right]\mathrm{m}\mathrm{o}\mathrm{d}998244353$$
我們對$i\mathrm{m}\mathrm{o}\mathrm{d}4$的值進行分別討論，我們現在要求的就是各組的系數和
我們現在要求
$$\left[\sum _{i=0}^n\left(\left(\genfrac{}{}{0ex}{}{n}{i}\right)?s^i[4|i]\right)\right]\mathrm{m}\mathrm{o}\mathrm{d}998244353$$
$$\begin{array}{rl}\sum _{i=0}^n\left(\left(\genfrac{}{}{0ex}{}{n}{i}\right)?s^i[4|i]\right)& =\sum _{i=0}^n\left(\left(\genfrac{}{}{0ex}{}{n}{i}\right)?s^i\frac{1}{4}\sum _{j=0}^{4?1}({\omega }_4^i{)}^j\right)\\ & =\frac{1}{4}\sum _{j=0}^3\sum _{i=0}^n\left(\left(\genfrac{}{}{0ex}{}{n}{i}\right)?s^i({\omega }_4^j{)}^i\right)\\ & =\frac{1}{4}\sum _{j=0}^3{\left(s{\omega }_4^j+1\right)}^n\end{array}$$
那么單個的系數就求得了，那么我們發現除了$[4|i]$的情況，還有$[4|i?1]$,$[4|i?2]$,$[4|i?3]$的情況，那么相當于是我們將關于$x={\omega }_4^j$的函數的值分別乘以$x^{?1}，x^{?2}，x^{?3}$，然后（具體做法是，對于$x={\omega }_4^i$，$x^{?1}={\omega }_4^{?i}$），其它的一樣做即可

代碼

#include<bits/stdc++.h> typedef long long ll; #define rg register template <typename T> inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;} template <typename T> inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');} template <typename T> inline void print(const T x){if(x<0)putchar('-'),printe(-x);else printe(x);} const ll mod=998244353; ll T,n,s,a0,a1,a2,a3,w0,w1,w2,w3,inv; inline ll pow(ll x,ll y) {ll res=1;for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;return res; } int main() {read(T);w0=1,w1=pow(3,(mod-1)/4),w2=w1*w1%mod,w3=w1*w2%mod;inv=pow(4,mod-2);while(T--){read(n),read(s),read(a0),read(a1),read(a2),read(a3);const ll k0=pow(s*w0%mod+1,n),k1=pow(s*w1%mod+1,n),k2=pow(s*w2%mod+1,n),k3=pow(s*w3%mod+1,n);ll ans=0;ans=(ans+(k0*w0+k1*w0+k2*w0+k3*w0)%mod*a0)%mod;ans=(ans+(k0*w0+k1*w3+k2*w2+k3*w1)%mod*a1)%mod;ans=(ans+(k0*w0+k1*w2+k2*w0+k3*w2)%mod*a2)%mod;ans=(ans+(k0*w0+k1*w1+k2*w2+k3*w3)%mod*a3)%mod;print(ans*inv%mod),putchar('\n');}return 0; }

總結

單位根反演需要推式子，但寫起來比較清真

總結

以上是生活随笔為你收集整理的单位根反演[loj6485]LJJ 学二项式定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。