洛谷 P4238 https://www.luogu.org/problemnew/show/P4238
多项式求逆: http://blog.miskcoo.com/2015/05/polynomial-inverse
注意: 直接在点值表达下做 $B(x) \equiv 2B'(x) - A(x)B'^2(x) \pmod {x^n}$ 是可以的, 但是一定要注意, 这一步中有一个长度为 n 的和两个长度为 (n/2) 的多项式卷积, 因此要在 DFT 前就扩展 FFT 点值表达的 "长度" 到 2n, 否则会出错(调了 1.5 个小时)
备份
- #prag 2 ma GCC optimize(2)
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<vector>
- #include<cmath>
- using namespace std;
- #define fi first
- #define se second
- #define mp make_pair
- #define pb push_back
- typedef long long ll;
- typedef unsigned long long ull;
- const ll md=998244353;
- const int N=262145;
- int rev[N];
- void init(int len)
- {
- int bit=0,i;
- while((1<<(bit+1))<=len) ++bit;
- for(i=0;i<len;++i)
- rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
- }
- ll poww(ll a,ll b)
- {
- ll base=a,ans=1;
- for(;b;b>>=1,base=base*base%md)
- if(b&1)
- ans=ans*base%md;
- return ans;
- }
- void dft(ll *a,int len,int idx)// 要求 len 为 2 的幂
- {
- int i,j,k;ll t1,t2,wn,wnk;
- for(i=0;i<len;++i)
- if(i<rev[i])
- swap(a[i],a[rev[i]]);
- for(i=1;i<len;i<<=1)
- {
- wn=poww(idx==1?3:332748118,(md-1)/(i<<1));
- for(j=0;j<len;j+=(i<<1))
- {
- wnk=1;
- for(k=j;k<j+i;++k,wnk=wnk*wn%md)
- {
- t1=a[k];t2=a[k+i]*wnk%md;
- a[k]+=t2;
- (a[k]>=md) && (a[k]-=md);
- a[k+i]=t1-t2;
- (a[k+i]<0) && (a[k+i]+=md);
- }
- }
- }
- if(idx==-1)
- {
- ll ilen=poww(len,md-2);
- for(i=0;i<len;++i) (a[i]*=ilen)%=md;
- }
- }
- ll f[N],g[N],t1[N];
- int n,n1;
- void p_inv(ll *f,ll *g,int len)//g=f^(-1);f,g 长度不小于 2^(ceil(log2(len))+1)
- {
- g[0]=poww(f[0],md-2);
- for(int i=2,j;i<(len<<1);i<<=1)
- {
- init(i<<1);
- memcpy(t1,f,sizeof(ll)*i);
- memset(t1+i,0,sizeof(ll)*i);
- memset(g+(i>>1),0,sizeof(ll)*(i+(i>>1)));
- dft(t1,i<<1,1);dft(g,i<<1,1);
- for(j=0;j<(i<<1);++j)
- g[j]=g[j]*(2+(md-g[j])*t1[j]%md)%md;
- dft(g,i<<1,-1);
- }
- }
- int main()
- {
- int i,t;
- scanf("%d",&n);n1=n;
- for(i=0;i<n;++i)
- scanf("%lld",g+i);
- for(t=1;t<n;t<<=1);
- n=t;
- p_inv(g,f,n);
- for(i=0;i<n1;++i)
- printf("%lld",f[i]);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2946018.html