MnZn求助
查看原帖
MnZn求助
104662
PrincessQi楼主2021/3/12 17:01
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n,qwq,g=3,l,ig,il,fac[(1<<21)+5],inv[(1<<21)+5],r[(1<<21)+5],c[(1<<21)+5],a[(1<<21)+5],b[(1<<21)+5];
int ksm(int b,int p){
	int ans=1;
    while(p>0){
        if(p%2!=0)ans=ans*b%mod;
        b=b*b%mod;
        p=p>>1;  
    }
    return ans;
}
void nauseous_termagant_tle(int *a,int t){
	for(int i=0;i<l;i++)
		if(i<r[i])swap(a[i],a[r[i]]);
	for(int i=1;i<l;i<<=1){
		int x=ksm(t==1?g:ig,(mod-1)/(i<<1));
		for(int j=0;j<l;j+=(i<<1)){
			int y=1;
			for(int k=0;k<i;k++,y=x*y%mod){
				int p=a[j+k],q=y*a[j+k+i]%mod;
				a[j+k]=(p+q)%mod;
				a[j+k+i]=(p-q+mod)%mod;
			}
		}
	}
}
inline void polyinv(int deg,int *a,int *b){
	if(deg==1){
		b[0]=ksm(a[0],mod-2);
		return;
	}
	polyinv((deg+1)>>1,a,b);
	qwq=0;
	for(l=1;l<=deg+deg;l<<=1)qwq++;
	for(int i=0;i<deg;i++)
		r[i]=(r[i>>1]>>1)|((i&1)<<(qwq-1));
	for(int i=0;i<deg;i++)c[i]=a[i];
	for(int i=deg;i<l;i++)c[i]=0;
	nauseous_termagant_tle(b,1),nauseous_termagant_tle(c,1);
	for(int i=0;i<l;i++)
		b[i]=b[i]*(2-b[i]*c[i]%mod+mod)%mod;
	nauseous_termagant_tle(b,-1);
	il=ksm(l,mod-2);
	for(int i=0;i<l;i++)
		b[i]=b[i]*il%mod;
	for(int i=deg;i<l;i++)b[i]=0;
}
signed main(){
	ig=ksm(g,mod-2);
	scanf("%lld",&n);
	for(int i=0;i<n;i++)
		scanf("%lld",&a[i]);
	polyinv(n,a,b);
	for(int i=0;i<n;i++)
		printf("%lld ",b[i]);
	return 0;
}

样例都美过,自闭了

2021/3/12 17:01
加载中...