QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#844002#619. 多项式求逆linweitong0 267ms48664kbC++142.0kb2025-01-05 11:16:102025-01-05 11:16:11

Judging History

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

  • [2025-01-05 11:16:11]
  • 评测
  • 测评结果:0
  • 用时:267ms
  • 内存:48664kb
  • [2025-01-05 11:16:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000005,mod=998244353;
int ADD(int x,int y){return x+y>=mod?(x+y-mod):(x+y);}
int SUB(int x,int y){return x-y<0?(x-y+mod):(x-y);}
void add(int &x,int y){x=x+y>=mod?(x+y-mod):(x+y);}
void sub(int &x,int y){x=x-y<0?(x-y+mod):(x-y);}
namespace poly{
	const int g=3,ginv=(mod+1)/3,inv2=(mod+1)/2;
	int rev[N<<2],A[N<<2],B[N<<2];
	ull f[N<<2],w[N<<2];
	int ksm(int x,int y){
		int s=1;
		while (y){
			if (y&1)s=1ll*s*x%mod;
			x=1ll*x*x%mod;
			y>>=1;
		}
		return s;
	}
	void ntt(int n,int *a,int tp){
		for (int i=0;i<n;i++)f[i]=a[rev[i]];
		for (int i=1;i<n;i<<=1){
			int len=(i<<1),g1=ksm(tp==1?g:ginv,(mod-1)/len);
			w[0]=1;
			for (int j=1;j<i;++j)w[j]=w[j-1]*g1%mod;
			for (int j=0;j<n;j+=len){
				for (int k=0;k<i;++k){
					ull x=f[k|j],y=w[k]*f[k|i|j]%mod;
					f[k|j]+=y;
					f[k|i|j]=x+mod-y;
				}
			}
			if (i==(1<<17))for (int j=0;j<n;++j)f[j]%=mod;
		}
		if (tp==-1){
			int nn=ksm(n,mod-2);
			for (int i=0;i<n;i++)a[i]=f[i]%mod*nn%mod; 
		}
		else{
			for (int i=0;i<n;++i)a[i]=f[i]%mod;
		}
	}
	int calc(int a,int b,bool typ){return !typ?(1ll*a*b%mod):(1ll*a*((mod+2-1ll*a*b%mod)%mod)%mod);}
	void mul(int len,int *a,int *b,bool typ){
		len--;
		int n=1,s=0;while (n<=len+2)n<<=1,s++;
		rev[0]=0;for (int i=1;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(s-1));
		for (int i=0;i<n;i++)A[i]=(i<=len?a[i]:0),B[i]=(i<=len?b[i]:0);
		ntt(n,A,1),ntt(n,B,1);
		for (int i=0;i<n;i++)A[i]=calc(A[i],B[i],typ);
		ntt(n,A,-1);
		for (int i=0;i<n;++i)a[i]=(i<=len?A[i]:0);
		for (int i=0;i<n;i++)A[i]=B[i]=0;
	}
	void poly_inv(int n,int *a,int *b){
		if (n==1){b[0]=ksm(a[0],mod-2);return;}
		poly_inv((n+1)>>1,a,b);
		mul(n,b,a,1);
	}
}
int n,a[N<<2],m,b[N<<2];
const int mod2=mod-1;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for (int i=0;i<n;++i)cin>>a[i];
	poly::poly_inv(n,a,b);
	for (int i=0;i<n;++i)cout<<b[i]<<" ";
}

詳細信息


Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 15884kb

input:

100
321704272 732147873 495950455 607498198 139258053 834073875 837326587 9642661 903437916 207412353 359180940 720085797 719290810 723076036 984279000 503225771 350175866 162829281 512559053 225874248 808881115 775602122 556705696 16814894 894905093 985867138 253650922 979472539 59109787 205995179 ...

output:

224380241 407939914 948783212 252775436 244885128 619616506 740304620 834993645 133844614 554040828 466140652 112045865 718887485 15435832 136961435 41151855 421053335 221482226 535083421 973403549 230431196 423504380 642285957 978247424 413899488 802911919 441991818 393346051 498262759 325392726 10...

result:

wrong answer 1st numbers differ - expected: '890391751', found: '224380241'

Test #2:

score: 0
Wrong Answer
time: 4ms
memory: 15984kb

input:

5000
895174753 48640370 621768187 544696442 266653647 800854366 993400253 180889611 259138834 922465819 237366500 134204023 882884556 962623362 906378209 783980105 385064692 526608265 306798389 492937123 600567928 363960265 499995507 901802313 322681104 915889147 191761221 168327309 250045818 379937...

output:

860277067 957832531 754106931 16605881 228310346 263010761 737134167 748695281 229779334 697772619 699052605 972766144 380550423 504839042 396991031 51437302 528007066 686703407 201421759 667436502 697489394 852667958 786042231 983269553 197909318 170781547 658762845 549939643 543607598 827212872 55...

result:

wrong answer 1st numbers differ - expected: '682334353', found: '860277067'

Test #3:

score: 0
Wrong Answer
time: 10ms
memory: 18188kb

input:

30000
433849057 26933151 94119735 348782922 994201565 286266085 253836562 391505281 561460922 76317536 151770395 626212470 835627785 278418333 560388198 586773695 43090005 450934659 716357773 746228248 47588293 745422420 131896260 923566007 275614901 981279191 966289868 111837778 850083076 346727100...

output:

430031945 614042512 73094228 756482666 592892772 576533505 41747737 424568705 275111799 779440132 706385725 124142041 896237528 118911601 950175103 302243364 92146089 710578200 143854043 580498478 691228487 755488346 726931484 388861455 60455662 599879137 579782071 637631663 669499154 982715101 3420...

result:

wrong answer 1st numbers differ - expected: '357845866', found: '430031945'

Test #4:

score: 0
Wrong Answer
time: 30ms
memory: 18520kb

input:

100000
299085935 896290047 664961463 798136437 284888760 805376081 754380153 982440654 523416648 618138054 639229548 946675552 216492659 801950754 591895463 409803161 734598818 262678735 505505080 132772037 241184558 549895828 778274609 60046418 766879997 555641192 925835147 535599922 727361907 2850...

output:

710498441 186950744 125063349 92484237 46175087 682036824 288633254 451005342 219950044 439058842 206481212 981078640 283904333 109269843 831837854 711781469 800863230 157817967 787638835 223684657 437565439 684506609 571031115 584735724 155569672 201406266 990799847 390971014 771986589 27989228 502...

result:

wrong answer 1st numbers differ - expected: '152663231', found: '710498441'

Test #5:

score: 0
Wrong Answer
time: 267ms
memory: 48664kb

input:

1000000
737044976 941398691 939287417 273413335 175365852 377721127 3862986 176449650 791765055 129385383 433663518 447033570 279210233 157228851 130509370 963480863 130226624 349605390 600289609 890766355 577960206 537162643 776878360 951933771 688851169 624945579 212339598 106077966 426859950 6284...

output:

562917251 398013735 164609732 195952690 849324890 203143419 917517783 707394879 279282858 594770467 416831142 278065060 130712701 288214445 287002430 760165453 876779616 877526169 39636731 764421132 462835991 884453040 963430076 173578697 464990856 232104898 125226750 59004043 814581421 546931359 67...

result:

wrong answer 1st numbers differ - expected: '132989151', found: '562917251'