QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#92957#622. 多项式多点求值Appleblue17#40 2576ms318192kbC++148.8kb2023-03-31 09:17:312023-03-31 09:17:35

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-31 09:17:35]
  • 评测
  • 测评结果：40
  • 用时：2576ms
  • 内存：318192kb
查看
  • [2023-03-31 09:17:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long N=3e6+5,mod=998244353,inv2=499122177,g=3;
long long inv[N];
long long ksm(long long f,long long x){
	long long tot=1;
	while(x){
		if(x & 1ll) tot=tot*f%mod;
		f=f*f%mod;
		x>>=1ll;
	}
	return tot;
}
 
map <long long,long long> mp;
long long BSGS(long long a,long long p,long long n){
	mp.clear();
	long long m=ceil(sqrt(p)),tmp=1;
	for(long long i=0;i<m;i++) mp[tmp*n%p]=i+1,tmp=tmp*a%p;
	
	long long tmpp=1;
	for(long long i=0;i<=m;i++){
		if(mp[tmpp]) return i*m-mp[tmpp]+1;
		tmpp=tmpp*tmp%p;
	}
	return -1;
}
 
long long pr[N];
namespace NTT{
	long long A[N],B[N],rev[N];
	void pre(){
		for(long long l=1;l<N;l<<=1ll)
			pr[l]=ksm(g,(mod-1)/(l*2));
	}
	long long init(long long n,long long m){
		long long lim=0;
		while((1ll<<lim)<=n+m) lim++;
		for(long long i=0;i<=(1<<lim)-1;i++)
			rev[i]=(rev[i>>1ll]>>1ll) | ((i & 1ll)<<(lim-1));
		return lim;
	}
	void ntt(long long *f,long long n,long long opt){
		for(long long i=0;i<=n-1;i++)
			if(i<rev[i]) swap(f[i],f[rev[i]]);
		for(long long l=1;l<n;l<<=1ll){
			long long tmp=pr[l];
			if(opt==-1) tmp=ksm(tmp,mod-2);
			for(long long i=0;i<=n-1;i+=l<<1ll){
				long long omegf=1;
				for(long long j=0;j<l;j++){
					long long x=f[i+j],y=omegf*f[i+j+l]%mod;
					f[i+j]=(x+y)%mod,f[i+j+l]=(x-y+mod)%mod;
					omegf=omegf*tmp%mod;
				}
			}
		}
		if(opt==-1){
			long long t=ksm(n,mod-2);
			for(long long i=0;i<=n-1;i++)
				f[i]=f[i]*t%mod;
		}
	}
	void solve(long long *s,long long* f,long long* g,long long n,long long m){
		long long lim=init(n,m);
		for(long long i=0;i<=n;i++) A[i]=f[i];
		for(long long i=0;i<=m;i++) B[i]=g[i];
		for(long long i=n+1;i<=(1ll<<lim);i++) A[i]=0;
		for(long long i=m+1;i<=(1ll<<lim);i++) B[i]=0;
		ntt(A,(1<<lim),1);
		ntt(B,(1<<lim),1);
		for(long long i=0;i<=(1<<lim)-1;i++) s[i]=A[i]*B[i]%mod;
		ntt(s,(1<<lim),-1);
	}
}
 
namespace INV{
	long long A[N],B[N],S[N];
	void solve(long long *s,long long *f,long long n){
		S[0]=ksm(f[0],mod-2);
		S[1]=0;
		long long len;
		for(len=2;len<=(n<<1ll);len<<=1ll){
			//       ^^ 这里一定要写小于等于!
			//len是现在处理的长度（即x^n） 
			long long lim=len<<1ll;
			for(long long i=0;i<len;i++) A[i]=f[i],B[i]=S[i];
			for(long long i=len;i<lim;i++) A[i]=B[i]=0;
			NTT::init(len,0);
			NTT::ntt(A,lim,1);
			NTT::ntt(B,lim,1);
			for(long long j=0;j<lim;j++)
				S[j]=(2*B[j]+mod-A[j]*B[j]%mod*B[j]%mod)%mod;
			NTT::ntt(S,lim,-1);
			for(long long j=len;j<lim;j++) S[j]=0;
		}
		for(long long i=0;i<=n;i++) s[i]=S[i];
	}
}
namespace poly{
	void Add(long long *s,long long *f,long long *g,long long n,long long m){
		for(long long i=0;i<=max(n,m);i++) s[i]=(f[i]+g[i])%mod;
	}
	//加 
	void Del(long long *s,long long *f,long long *g,long long n,long long m){
		for(long long i=0;i<=max(n,m);i++) s[i]=(f[i]+mod-g[i])%mod;
	}
	//减 
	void Mult(long long *s,long long *f,long long n,long long k){
		for(long long i=0;i<=n;i++) s[i]=(f[i]*k%mod+mod)%mod;
	}
	//乘 
	void Rev(long long *s,long long *f,long long n){
		for(long long i=0;i<=n/2;i++) swap(f[i],f[n-i]);
	}
	//翻转 
	void Deriv(long long *s,long long *f,long long n){
		long long A[N];
		A[n]=0;
		for(long long i=1;i<=n;i++) A[i-1]=f[i]*i%mod;
		for(long long i=0;i<=n;i++) s[i]=A[i];
	}
	//求导 
	void Limit(long long *s,long long *f,long long n){
		long long A[N];
		A[0]=0;
		for(long long i=0;i<=n-1;i++) A[i+1]=f[i]*ksm(i+1,mod-2)%mod;
		for(long long i=0;i<=n;i++) s[i]=A[i];
	}
	//极限 
	void Div(long long *q,long long* r,long long *f,long long *g,long long n,long long m){
		long long A[N],B[N],C[N],D[N];
		for(long long i=0;i<=n;i++) A[i]=C[i]=f[i];
		for(long long i=0;i<=m;i++) B[i]=D[i]=g[i];
		Rev(A,A,n);
		Rev(B,B,m);
		INV::solve(B,B,n-m);
		NTT::solve(q,A,B,n,n-m);
		for(long long i=n-m+1;i<=n+n-m;i++) q[i]=0;
		Rev(q,q,n-m);
		
		NTT::solve(D,D,q,m,n-m);
		Del(r,C,D,n,n);
	}
	//带余除法 
	void Devide_solve(long long *s,long long *g,long long l,long long r){
		if(l==r) return ;
		long long mid=(l+r)>>1ll;
		Devide_solve(s,g,l,mid);
		
		long long lim=r-l+1,len=lim>>1ll;
		long long A[N],B[N];
		for(long long i=1;i<=len;i++) A[i]=s[l+i-1];
		for(long long i=1;i<=lim;i++) B[i]=g[i];
		NTT::solve(A,A,B,len,lim);
		for(long long i=len+1;i<=lim;i++) s[i-len+mid]=(s[i-len+mid]+A[i])%mod;
		
		Devide_solve(s,g,mid+1,r);
	}
	
	void Devide(long long *s,long long *g,long long n){
		long long lim=NTT::init(n,0);
		long long m=1ll<<lim;
		for(long long i=0;i<=m;i++) s[i]=0;
		s[1]=1;
		Devide_solve(s,g,1,m);
	}
	//分治NTT 
	void Ln(long long *s,long long *f,long long n){
		long long A[N],B[N];
		long long lim=NTT::init(n,n);
		for(long long i=0;i<=n;i++) A[i]=f[i],B[i]=0;
		for(long long i=n+1;i<(1ll<<lim);i++) A[i]=B[i]=0;
		Deriv(B,A,n);
		INV::solve(A,A,n);
		NTT::solve(A,A,B,n,n);
		Limit(A,A,n);
		for(long long i=0;i<=n;i++) s[i]=A[i];
	}
	//分治+NTT 
	vector <long long> P[N];
	void solve(long long n,long long o,long long l,long long r){
		long long len=r-l+1;
		P[o].resize(4*len+2);
		
		if(l==r){
			if(l<=n) P[o]={l-1,1};//在这里改 
			else P[o]={1};
			return ;
		}
		long long mid=(l+r)>>1;
		solve(n,o<<1,l,mid);
		solve(n,o<<1|1,mid+1,r);
		
		NTT::solve(P[o].data(),P[o<<1].data(),P[o<<1|1].data(),len>>1,len>>1);
	}
	//对数 
	void Sqrt(long long *s,long long *f,long long n){
		long long A[N],B[N],C[N],S[N];
		
		long long p=BSGS(3,998244353,f[0]);
		
		S[0]=ksm(3,p/2);
		S[1]=0;
		long long len;
		
		for(len=1;len<=(n<<1ll);len<<=1ll){
			long long lim=len<<1ll;
			for(long long i=0;i<len;i++) A[i]=f[i],B[i]=S[i];
			for(long long i=len;i<lim;i++) A[i]=B[i]=C[i]=0;
			
			INV::solve(C,B,len);
			NTT::init(len,0);
			NTT::ntt(A,lim,1);
			NTT::ntt(C,lim,1);
			for(long long j=0;j<lim;j++) S[j]=A[j]*C[j]%mod;
			NTT::ntt(S,lim,-1);
			
			for(long long i=0;i<lim;i++) S[i]=(S[i]+B[i])%mod*inv2%mod;
			for(long long j=len;j<lim;j++) S[j]=0;
			
		}
		for(long long i=0;i<=n;i++) s[i]=S[i];
	}
	//开根 
	void Exp(long long *s,long long *f,long long n){
		long long A[N],B[N],C[N],S[N];
		S[0]=1;
		S[1]=0;
		long long len;
		
		for(len=2;len<=(n<<1ll);len<<=1ll){
			long long lim=len<<1ll;
			for(long long i=0;i<len;i++) A[i]=f[i],B[i]=S[i];
			for(long long i=len;i<lim;i++) A[i]=B[i]=C[i]=0;
			
			Ln(C,B,len-1);
			for(long long i=0;i<len;i++) C[i]=(mod-C[i]+A[i])%mod;
			C[0]=(C[0]+1)%mod;
			NTT::init(len,0);
			NTT::ntt(B,lim,1);
			NTT::ntt(C,lim,1);
			for(long long j=0;j<lim;j++) S[j]=B[j]*C[j]%mod;
			
			NTT::ntt(S,lim,-1);
			for(long long j=len;j<lim;j++) S[j]=0;
		}
		for(long long i=0;i<=n;i++) s[i]=S[i];
	}
	//指数 
	void Pow(long long *s,long long *f,long long n,long long k1,long long k2,long long lenk){
		long long A[N];
		long long lim=NTT::init(n,n);
		for(long long i=n+1;i<(1ll<<lim);i++) A[i]=0;
		
		long long t=0;
		while(!f[t]) t++;
		if(lenk>log(n) && t){
			for(long long i=0;i<=n;i++) s[i]=0;
			return ;
		}
		
		long long p=ksm(f[t],k2),q=ksm(f[t],mod-2);
		n-=t;
		for(long long i=0;i<=n;i++) A[i]=f[i+t]*q%mod;
		
		Ln(A,A,n);
		Mult(A,A,n,k1);
		Exp(A,A,n);
		for(long long i=0;i+t*k1<=n+t;i++)
		  s[i+t*k1]=A[i]*p%mod;
	}
	//快速幂
}



namespace Evaluation{
	long long tmp[N];
	vector <long long> P[N],Q[N];
	long long lenp[N],lenq[N];
	void init(long long o,long long l,long long r){
		long long len=r-l+1,mid=(l+r)>>1ll;
		lenp[o]=len;
		lenq[o]=len-1;
		P[o].resize(2*lenp[o]+2);
		Q[o].resize(2*lenq[o]+2);
		if(l==r) return ;
		init(o<<1,l,mid);
		init(o<<1|1,mid+1,r);
	}
	
	void solve1(long long *a,long long m,long long o,long long l,long long r){
		long long len=r-l+1;	
		if(l==r){
			if(l<=m) P[o]={(mod-a[l])%mod,1};
			else P[o]={1};
			return ;
		}
		long long mid=(l+r)>>1;
		solve1(a,m,o<<1,l,mid);
		solve1(a,m,o<<1|1,mid+1,r);
		NTT::solve(P[o].data(),P[o<<1].data(),P[o<<1|1].data(),lenp[o<<1],lenp[o<<1|1]);
	}
	
	void solve2(long long *s,long long o,long long l,long long r){
		long long len=r-l+1;
		if(l==r){
			s[l]=Q[o][0];
			return ;
		}
		long long mid=(l+r)>>1;
		poly::Div(tmp,Q[o<<1].data(),Q[o].data(),P[o<<1].data(),lenq[o],lenp[o<<1]);
		poly::Div(tmp,Q[o<<1|1].data(),Q[o].data(),P[o<<1|1].data(),lenq[o],lenp[o<<1|1]);
		solve2(s,o<<1,l,mid);
		solve2(s,o<<1|1,mid+1,r);
	}
	void solve(long long *s,long long *f,long long *a,long long n,long long m){
		init(1,1,m);
		solve1(a,m,1,1,m);
		poly::Div(tmp,Q[1].data(),f,P[1].data(),n,lenp[1]);
		solve2(s,1,1,m);
	}
}

long long n,m;
long long f[N],a[N],ans[N];

int main(){
	NTT::pre();
	cin>>n>>m; n--;
	for(long long i=0;i<=n;i++) scanf("%lld",&f[i]);
	for(long long i=1;i<=m;i++) scanf("%lld",&a[i]);
	Evaluation::solve(ans,f,a,n,m);
	
	for(long long i=1;i<=m;i++) printf("%lld\n",ans[i]);
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 20
Accepted
time: 91ms
memory: 312736kb

input:

100 94
575336069 33153864 90977269 80162592 25195235 334936051 108161572 14050526 356949084 797375084 805865808 286113858 995555121 938794582 458465004 379862532 563357556 293989886 273730531 13531923 113366106 126368162 405344025 443053020 475686818 734878619 338356543 661401660 834651229 527993675...

output:

940122667
397187437
905033404
346709388
146347009
49596361
125616024
966474950
693596552
162411542
248699477
217639076
254290825
963991654
951375739
431661136
587466850
933820245
135676159
683994808
821695954
675479292
463904298
15085475
183389374
976945620
668527277
98940366
909505808
904450031
968...

result:

ok 94 numbers

Test #2:

score: 20
Accepted
time: 2576ms
memory: 318192kb

input:

5000 4999
410683245 925831211 726803342 144364185 955318244 291646122 334752751 893945905 484134283 203760731 533867267 813509277 491860093 413174124 584582617 594704162 976489328 978500071 196938934 628117769 169796671 858963950 562124570 582491326 647830593 238623335 20782490 674939336 656529076 2...

output:

683038054
713408290
776843174
52275065
602085453
905088100
991748340
720305324
831850056
296147844
79380797
882313010
941965313
987314872
363655479
380838721
51243733
165728533
592641557
679475455
651115426
60492203
787012426
247557193
136399242
484592897
908383514
735275879
648228244
443933835
5504...

result:

ok 4999 numbers

Test #3:

score: 0
Time Limit Exceeded

input:

30000 29995
536696866 881441742 356233606 594487396 991820796 695996817 7219464 149265950 843761437 329761701 260625152 80366362 598729314 133794090 12808683 67477659 320740422 878134577 879383179 940923483 660160621 18082378 886078389 524050341 35092018 137623841 988429688 258507355 138475726 75726...

output:

result:

Test #4:

score: 0
Time Limit Exceeded

input:

100000 99989
703908936 826436271 431732352 607460686 960390248 897906950 506352459 662618885 172508812 713410533 704313866 156459539 879660919 98030681 46358006 400134234 121190289 498201666 616888945 210891377 39623412 687350951 269444705 980768130 381802923 553892268 644461704 287608268 554761733 ...

output:

result:

Test #5:

score: 0
Time Limit Exceeded

input:

1000000 999998
326289172 459965021 432610030 381274775 890620650 133203219 755508578 820410129 100497878 978894337 34545975 484258543 341383383 556328539 705716773 985485996 201697555 806763870 456757110 445252781 501965590 655584951 516373423 475444481 554722275 106826011 433893131 385018453 687541...

output:

result:
English 繁體中文 简体中文

Server Time: 2025-02-02 01:05:34 | OpenSource Project