QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#589904#621. 多项式指数函数leingy5an80 1704ms32068kbC++173.7kb2024-09-25 20:33:142024-09-25 20:33:16

Judging History

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

  • [2024-09-25 20:33:16]
  • 评测
  • 测评结果:80
  • 用时:1704ms
  • 内存:32068kb
  • [2024-09-25 20:33:14]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>

#define ll long long
#define _it set<node>::iterator
#define N 3000006

using namespace std;

inline long long read(){
	ll f=1,s=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
	return s*f;
}

namespace polygone{
	
	const double pi=acos(-1.0);
	const long long  mod = 998244353, g = 3, g1 = 332748118;
	ll add(ll x,ll y){x+=y;return x>=mod?x-mod:x;}
	ll rdu(ll x,ll y){x-=y;return x<0?x+mod:x;}
	ll mul(ll x,ll y){return 1ll*x*y%mod;}
	
	#define poly vector<ll>
	#define plen(x) ((int)x.size())
	
	ll finv[N],r[N],lim,lg;
	
	ll qpow(ll x,ll y){
		if(y==1) return x;
		ll res=qpow(x,y>>1);
		if(y&1) return (((res*res)%mod)*x)%mod;
		return (res*res)%mod;
	}ll ginv(ll x){return qpow(x,mod-2);}
	
	void init(ll n){
		for(lim=1,lg=0;lim<=n;lim<<=1,lg++);
		for(int i=0;i<lim;i++) r[i]=((r[i>>1]>>1)|((i&1)<<(lg-1)));
	}
	
	void cinv(ll n){
		finv[1]=1;
		for(int i=2;i<=n;i++) finv[i]=mul(mod-mod/i,finv[mod%i]);
	}
	
	poly operator - (ll x,poly f){ll len=plen(f);for(int i=0;i<len;i++) f[i]=mod-f[i];f[0]=add(f[0],x);return f;}
	poly operator - (poly f,ll x){f[0]=rdu(f[0],x);return f;}
	poly operator - (poly f,poly g){ll n=max(plen(f),plen(g));f.resize(n);g.resize(n);for(int i=0;i<n;i++) f[i]=rdu(f[i],g[i]);return f;}
	poly operator * (poly f,ll x){ll len=plen(f);for(int i=0;i<len;i++) f[i]=mul(f[i],x);return f;}
	poly operator + (poly f,poly g){ll n=max(plen(f),plen(g));f.resize(n);g.resize(n);for(int i=0;i<n;i++) f[i]=add(f[i],g[i]);return f;}
	
	void ntt(poly &f,int op){
		for(int i=0;i<lim;i++) if(i<r[i]) swap(f[i],f[r[i]]);
		for(int mid=1;mid<lim;mid<<=1){
			ll wn=qpow(op==1?g:g1,(mod-1)/(mid<<1));
			for(int j=0;j<lim;j+=(mid<<1)){
				ll w=1;
				for(int k=0;k<mid;k++,w=(w*wn)%mod){
					ll x=f[j+k],y=w*f[j+k+mid]%mod;
					f[j+k]=(x+y)%mod;
					f[j+k+mid]=(x-y+mod)%mod;
				}
			}
		}
		if(op==1) return;
		ll inv=qpow(lim,mod-2);
		for(int i=0;i<lim;i++) f[i]=1ll*f[i]*inv%mod;
	}
	
	poly operator * (poly f,poly g){
		ll n=plen(f)+plen(g)-1;
		init(n);
		f.resize(lim);g.resize(lim);
		ntt(f,1);ntt(g,1);
		for(int i=0;i<lim;i++) f[i]=mul(f[i],g[i]);
		ntt(f,-1);
		f.resize(min(n,1ll*100000)); 
		return f;
	}
	
	poly inv(poly f){
		poly g=poly(1,ginv(f[0]));
		ll len=plen(f);
		for(int i=2;i<(len<<1);i<<=1){
			poly A=f;
			A.resize(i);
			g=g*(2-(g*A));
		}
		g.resize(len);
		return g;
	}
	
	poly qiudao(poly f){
		ll len=plen(f);
		for(int i=0;i<len-1;i++) f[i]=mul(i+1,f[i+1]);
		f.resize(len-1);
		return f;
	}
	
	poly jifen(poly f){
		ll len=plen(f);
		f.resize(len+1);
		for(int i=len-1;i>=1;i--) f[i]=mul(f[i-1],finv[i]);
		f[0]=0;
		return f;
	}
	
	poly ln(poly f){
		poly g=jifen(qiudao(f)*inv(f));
		g.resize(plen(f));
		return g;
	}
	
	poly exp(poly f){
		poly g=poly(1,1);
		ll len=plen(f);
		for(int i=2;i<(len<<2);i<<=1){
			poly A=f;
			A.resize(i);
			g=g*((1-ln(g))+A);
		}
		g.resize(len);
		return g;
	}
	
	poly Pow(poly f,ll k){
		f=ln(f);f=f*k;f=exp(f);
		return f;
	}
	
	poly sqrt(poly f){
		poly g=poly(1,1);
		ll len=plen(f);
		ll inv2=ginv(2);
		for(int i=2;i<(len<<2);i<<=1){
			poly A=f;
			A.resize(i);
			g=(g+(A*inv(g)))*inv2;
		}
		g.resize(len);
		return g;
	}
}
using namespace polygone;
ll n,a[N],m,b[N],k;
poly f;

int main(){
	n=read();f.reserve(n);
	for(int i=1;i<=n;i++){
		ll x=read();
		f.push_back(x);	
	}
	cinv(n);
	f=exp(f);
	for(int i=0;i<n;i++) cout<<f[i]<<" ";
	return 0;
}

詳細信息


Pretests


Final Tests

Test #1:

score: 20
Accepted
time: 2ms
memory: 7684kb

input:

100
0 158447743 737554986 671332600 489297184 754299210 115728600 816221630 819073359 691660913 910093246 562505672 355119917 385019894 611338034 123976316 122342952 82142434 796101450 994778874 575255638 493217967 652609142 662045597 783871340 470398790 241710709 754059035 534582325 836438174 95789...

output:

1 158447743 989903074 918187254 200068193 455062373 11196740 759336019 312075964 992242039 123230223 144998958 189062409 420150911 170942299 432890803 760087114 639614944 787205333 63667632 243571846 141993017 450288335 173318832 743144111 879389773 95666186 453410000 569486107 512729334 226210545 5...

result:

ok 100 numbers

Test #2:

score: 20
Accepted
time: 227ms
memory: 19400kb

input:

5000
0 354399910 26360255 630255958 717224815 366941345 333979504 905420494 38176634 475666562 611197455 433060682 509600868 845217181 520468365 529689763 431747498 192834976 685184103 287994809 273221518 522219732 427553800 10872482 525061651 448069946 183539744 610476003 840167561 241104955 404100...

output:

1 354399910 51676417 184411965 928033808 589971658 936383703 745898312 943454394 65252947 270867254 772620225 995104944 58521883 96491645 326592384 283913887 140742590 960115688 684602174 623426872 184484323 952879775 315489867 167038509 580362327 164714100 833258994 345402076 261957154 469710461 98...

result:

ok 5000 numbers

Test #3:

score: 20
Accepted
time: 750ms
memory: 26140kb

input:

30000
0 147199510 293972908 780683378 633744119 800282266 162025013 919460711 939176222 298044997 277962122 729446209 455723129 756791462 84697115 579989768 945113433 549318980 229266945 869577376 103161009 960973464 440149102 836285074 687333626 638404974 184096947 370164754 454531549 142629528 150...

output:

1 147199510 30930552 734023222 564008583 299902819 450980389 806779390 654937901 981162061 206882721 35851319 707998765 357594654 305814262 734562024 591099032 543969413 539432668 154163976 451201740 856569012 898961429 732819402 243444529 673245321 601964526 206333661 876679409 438174247 903706710 ...

result:

ok 30000 numbers

Test #4:

score: 20
Accepted
time: 1704ms
memory: 32068kb

input:

100000
0 279349013 196667718 617497154 78288698 996674429 180463729 304956112 173800460 352061138 224505321 119706982 726737325 564797383 757014824 888433954 747100108 723246918 645172013 184990722 321964667 456686646 138153830 701558524 317746193 650472945 49496183 864461799 982372868 582778782 242...

output:

1 279349013 426120005 205100346 421201310 474118168 879116053 749708347 23319122 872190753 903275287 797670709 327019687 707029564 46014243 838268797 28223150 48499086 927009654 52188573 200586020 4624185 827007182 201682326 552029133 820855946 97607062 601649418 37529652 24405665 116064030 62051631...

result:

ok 100000 numbers

Test #5:

score: 0
Time Limit Exceeded

input:

1000000
0 204517192 162156394 729093416 352181074 335898409 357987855 386581690 26622360 437289663 34104646 938411413 659876244 293619518 291093969 909364118 179765868 89417259 632261731 375051702 493701794 771716785 682264158 329653513 86558030 9195128 957504298 22555222 384175297 128022431 5957444...

output:


result: