三模数NTT WA 0pts求助
查看原帖
三模数NTT WA 0pts求助
526677
封禁用户楼主2023/7/11 07:36
#include<bits/stdc++.h>
using namespace std;
#define N 114514
#define M 19198100
#define ll long long
#define re register int
ll n,m,p,a[M],b[M],r[M],ans[4][M];
//const ll A=998244353,B=469762049,C=1004535809,g=3; //三个原根为3的的1e9的模数
const ll P[3]={998244353,469762049,1004535809};
ll qpow(ll a,ll b,ll mod){
	ll ans=1;
	//cout<<"QWQ";
	while(b){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
//板子 
void NTT(ll n,ll *a,ll mod,ll g){
	for(ll i=0;i<n;++i)
		if(i<r[i]) swap(a[i],a[r[i]]); //位逆序置换
	for(ll i=2,h=1;i<=n;i<<=1,h<<=1){
		ll w=qpow(g,(mod-1)/i,mod);
		for(ll j=0;j<n;j+=i){
			ll W=1;
			for(ll k=0;k<h;++k,W=W*w%mod){
				ll x=a[j+k],y=W*a[h+j+k]%mod;
				a[j+k]=(x+y)%mod;
				a[h+j+k]=(x-y+mod)%mod;
			}
		}
	}
	//for(ll i=0;i<=n;++i) cout<<a[i]<<" ";
	//cout<<'\n';
}
ll x[M],y[M];
void work(ll n,ll *a,ll *b,ll mod,ll *ans){
	memcpy(x,a,n*sizeof(ll));
    memcpy(y,b,n*sizeof(ll));
	NTT(n,x,mod,3);
	NTT(n,y,mod,3);
	for(ll i=0;i<n;++i) x[i]=(ll)x[i]*y[i]%mod;//如果写的是int这里转成longlong一定要加
	NTT(n,x,mod,qpow(3,mod-2,mod));
	ll inv=qpow(n,mod-2,mod); //还是逆元
	for(ll i=0;i<n;++i) ans[i]=(ll)x[i]*inv%mod;
}
int main(){
	//三模数NTT 
	cin>>n>>m>>p;
	for(ll i=0;i<=n;++i) cin>>a[i];
	for(ll i=0;i<=m;++i) cin>>b[i];
	ll l=0,k=1;
	while(k<=n+m) k<<=1,l++;
	for(ll i=0;i<k;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	ll A=P[0],B=P[1],C=P[2];
	//根据CRT,通过三个序列得到确定的数 
	work(k,a,b,A,ans[0]);
	work(k,a,b,B,ans[1]);
	work(k,a,b,C,ans[2]);
	for(ll i=0;i<=n+m;++i){ //头晕柿子
		/*  EXCRT合并三个序列 
			Ai+k1*p1=Bi+k2*p2
			Ai+k1*p1≡Bi(mod p2)
			k1≡(Bi-Ai)/p1 (mod p2)
			得前两项解u=A1+k1*p1
		*/
		ll u=ans[0][i]+((ans[1][i]-ans[0][i]+B)*qpow(A,B-2,B)%B)*A;
		/*
			u+k3*p1*p2=Ci+k4*p3
			u+k3*p1*p2≡Ci(mod p3)
			k3≡(Ci-u)/(p1*p2) (mod p3)
			得道三项通解v=u+k3*p1*p2
			ans=v%p 
		*/
		ll v=(u%p+(ans[2][i]-u%C+C)*qpow(A*B,C-2,C)%C*A%p*B%p)%p;
		cout<<v<<" ";
	}
	return 0;
}
/*
5 8 28
19 32 0 182 99 95
77 54 15 3 98 66 21 20 38
*/
2023/7/11 07:36
加载中...