求调多项式乘法逆
查看原帖
求调多项式乘法逆
230875
Surge_of_Force楼主2022/6/7 21:53

蒟蒻真心求助,已经调了inf小时了



#include<bits/stdc++.h>
#define ll long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define int long long
#define orz cout<<"I AK IOI\n"
const int MAX=4e5+10;
const int MOD=998244353,g=3;
using namespace std;
inline char readchar() {
	static char buf[100000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
	int res = 0, f = 0;
	char ch = readchar();
	for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
	for(; isdigit(ch); ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
	return f ? -res : res;
}
inline void write(int x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int aa[MAX],r[MAX],bb[MAX],c[MAX];
int ksm(int ds,int zs)
{
	int ret=1;
	while(zs)
	{
		if(zs&1) ret=(ret*ds)%MOD;
		zs>>=1;ds=(ds*ds)%MOD;
	}
	return ret;
}
void NTT(int *t,int lim,bool f)
{
	for(int i=0;i<=lim;i++) if(r[i]>i) swap(t[i],t[r[i]]);
	for(int mid=1;mid<lim;mid<<=1)
	{
		int w0=ksm(f?g:ksm(3,MOD-2),(MOD-1)/(mid<<1));
		for(int R=mid<<1,j=0;j<lim;j+=R)
		{
			int w=1;
			for(int k=0;k<mid;k++,w=(w*w0)%MOD)
			{
				int x=t[k+j],y=w*t[mid+j+k]%MOD;
				t[k+j]=(x+y)%MOD;t[mid+j+k]=(x-y+MOD)%MOD;
			}
		}
	}
	return ;
}
void work(int deg,int *a,int *b)
{
	if(deg==1) return b[0]=ksm(a[0],MOD-2),void();
	work((deg+1)>>1,a,b);
	int len=0,lim=1;
	while(lim<=deg) lim<<=1,++len;
	for(int i=1;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(len-1));
	for(int i=0;i<deg;i++) c[i]=a[i];
	for(int i=deg;i<lim;i++) c[i]=0;
	NTT(c,lim,1);NTT(b,lim,1);
	for(int i=0;i<lim;i++) b[i]=(2-c[i]*b[i]%MOD+MOD)*b[i]%MOD;
	NTT(b,lim,0);
	for(int i=deg;i<lim;i++) b[i]=0;
}
signed main()
{
	int n=read();
	for(int i=0;i<n;i++) aa[i]=read();
	work(n,aa,bb);
	for(int i=0;i<n;i++) cout<<bb[i]<<' ';
	return 0;
}


2022/6/7 21:53
加载中...