NTT板子TLE求调
查看原帖
NTT板子TLE求调
311306
dk_qwq楼主2023/4/11 09:32

莫名T掉了最后两个点/kk

#include<iostream>
#include<cstdio>
using namespace std;
namespace INPUT{
	char buf[1<<20],*p1,*p2;
	#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin)),p1==p2?EOF:*p1++)
}
using namespace INPUT;
template<typename T>
inline T read(){
	T x=0,p=1;
	char ch=gc();
	while(ch<'0'||ch>'9'){
		if(ch=='-') p=-1;
		ch=gc();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=gc();
	}
	return x*p;
}
#define ll long long
ll ExGcd(ll a,ll b,ll &x,ll &y){
	if(!b) return x=1,y=0,a;
	ll r=ExGcd(b,a%b,y,x);
	y-=(a/b)*x;
	return r;
}
ll Inv(ll a,ll m){
	ll x,y;
	ExGcd(a,m,x,y);
	return (x%m+m)%m;
}
ll g,gi,p=998244353;
ll qpow(ll x,ll k){
	ll ans=1;
	while(k){
		if(k&1) ans=(ans*x)%p;
		x=(x*x)%p,k>>=1;
	}
	return ans;
}
const int N=4e6+5;
int r[N],limit,l;
void NTT(ll *A,int type){
	for(int i=0;i<limit;i++)
		if(i<r[i]) swap(A[i],A[r[i]]);
	for(int mid=1;mid<limit;mid<<=1){
		ll Wn=qpow(type==1?g:gi,(p-1)/(mid<<1));
		for(int R=mid<<1,j=0;j<limit;j+=R){
			ll w=1;
			for(int k=0;k<mid;k++,w=(w*Wn)%p){
				ll x=A[j+k],y=A[j+k+mid]*w%p;
				A[j+k]=(x+y)%p,A[j+k+mid]=(x-y+p)%p;
			}
		}
	}
	if(type==-1){
		ll Inl=Inv(limit,p);
		for(int i=0;i<limit;i++) A[i]=(A[i]*Inl)%p;
	}
}
ll A[N],B[N];
int n,m;
int main(){
//	freopen("P3803.in","r",stdin);
	g=3,gi=Inv(3,p);
	n=read<int>(),m=read<int>();
	for(int i=0;i<=n;i++) A[i]=read<int>();
	for(int i=0;i<=m;i++) B[i]=read<int>();
	limit=1;
	while(limit<=n+m) limit<<=1,l++;
	for(int i=0;i<limit;i++) r[i]=((r[i>>1]>>1)|((i&1)<<(l-1)));
	NTT(A,1),NTT(B,1);
	for(int i=0;i<limit;i++) A[i]=(A[i]*B[i])%p;
	NTT(A,-1);
	for(int i=0;i<=n+m;i++) printf("%lld%c",A[i]," \n"[i==n+m]);
}
2023/4/11 09:32
加载中...