QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#65520#5097. 小 P 爱学习feecle64180 739ms8296kbC++236.8kb2022-12-01 16:17:192022-12-01 16:39:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-01 16:39:12]
  • 评测
  • 测评结果：0
  • 用时：739ms
  • 内存：8296kb
查看
  • [2022-12-01 16:17:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,N=160000;
namespace Conv_998244353{

const int mod=998244353,g=3,invg=((mod+1)%3==0?(mod+1)/3:(2*mod+1)/3);
int wk[4105],ta[4105],tb[4105];
int Power(int x,int y){
	int r=1;
	while(y){
		if(y&1)r=1ll*r*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return r;
}
void DFT(int *a,int n){
	for(int i=n>>1;i;i>>=1){
		int w=Power(g,(mod-1)/(i<<1));
		wk[0]=1;
		for(int j=1;j<i;j++)wk[j]=1ll*wk[j-1]*w%mod;
		for(int j=0;j<n;j+=(i<<1)){
			for(int k=0;k<i;k++){
				int x=a[j+k],y=a[i+j+k],z=x;
				x+=y,(x>=mod&&(x-=mod)),a[j+k]=x;
				z-=y,(z<0&&(z+=mod)),a[i+j+k]=1ll*z*wk[k]%mod;
			}
		}
	}
}
void IDFT(int *a,int n){
	for(int i=1;i<n;i<<=1){
		int w=Power(invg,(mod-1)/(i<<1));
		wk[0]=1;
		for(int j=1;j<i;j++)wk[j]=1ll*wk[j-1]*w%mod;
		for(int j=0;j<n;j+=(i<<1)){
			for(int k=0;k<i;k++){
				int x=a[j+k],y=1ll*a[i+j+k]*wk[k]%mod,z=x;
				x+=y,(x>=mod&&(x-=mod)),a[j+k]=x;
				z-=y,(z<0&&(z+=mod)),a[i+j+k]=z;
			}
		}
	}
	for(int i=0,inv=Power(n,mod-2);i<n;i++)a[i]=1ll*a[i]*inv%mod;
}
int tta[2][15][4105],sz[2];
vector<int> conv(vector<int> A,int op){
	for(auto &i:A)i%=mod;
	int sa=A.size();
	vector<int> ret(sa+sz[op]-1);
	int len=1,o=0;
	while(len<ret.size())len<<=1,o++;
	for(int i=0;i<len;i++)ta[i]=tb[i]=0;
	for(int i=0;i<sa;i++)tb[i]=A[i];
	memcpy(ta,tta[op][o],sizeof(ta));
	DFT(tb,len);
	for(int i=0;i<len;i++)ta[i]=1ll*ta[i]*tb[i]%mod;
	IDFT(ta,len);
	for(int i=0;i<ret.size();i++)ret[i]=ta[i];
	return ret;
}
void init(vector<int> A,int op){
	for(auto &i:A)i%=mod;
	sz[op]=A.size();
	for(int j=0;j<=12;j++){
		for(int i=0;i<A.size();i++)tta[op][j][i]=A[i];
		DFT(tta[op][j],4096);
	}
}

}
namespace Conv_1004535809{

const int mod=1004535809,g=3,invg=((mod+1)%3==0?(mod+1)/3:(2*mod+1)/3);
int wk[4105],ta[4105],tb[4105];
int Power(int x,int y){
	int r=1;
	while(y){
		if(y&1)r=1ll*r*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return r;
}
void DFT(int *a,int n){
	for(int i=n>>1;i;i>>=1){
		int w=Power(g,(mod-1)/(i<<1));
		wk[0]=1;
		for(int j=1;j<i;j++)wk[j]=1ll*wk[j-1]*w%mod;
		for(int j=0;j<n;j+=(i<<1)){
			for(int k=0;k<i;k++){
				int x=a[j+k],y=a[i+j+k],z=x;
				x+=y,(x>=mod&&(x-=mod)),a[j+k]=x;
				z-=y,(z<0&&(z+=mod)),a[i+j+k]=1ll*z*wk[k]%mod;
			}
		}
	}
}
void IDFT(int *a,int n){
	for(int i=1;i<n;i<<=1){
		int w=Power(invg,(mod-1)/(i<<1));
		wk[0]=1;
		for(int j=1;j<i;j++)wk[j]=1ll*wk[j-1]*w%mod;
		for(int j=0;j<n;j+=(i<<1)){
			for(int k=0;k<i;k++){
				int x=a[j+k],y=1ll*a[i+j+k]*wk[k]%mod,z=x;
				x+=y,(x>=mod&&(x-=mod)),a[j+k]=x;
				z-=y,(z<0&&(z+=mod)),a[i+j+k]=z;
			}
		}
	}
	for(int i=0,inv=Power(n,mod-2);i<n;i++)a[i]=1ll*a[i]*inv%mod;
}
int tta[2][15][4105],sz[2];
vector<int> conv(vector<int> A,int op){
	for(auto &i:A)i%=mod;
	int sa=A.size();
	vector<int> ret(sa+sz[op]-1);
	int len=1,o=0;
	while(len<ret.size())len<<=1,o++;
	for(int i=0;i<len;i++)ta[i]=tb[i]=0;
	for(int i=0;i<sa;i++)tb[i]=A[i];
	memcpy(ta,tta[op][o],sizeof(ta));
	DFT(tb,len);
	for(int i=0;i<len;i++)ta[i]=1ll*ta[i]*tb[i]%mod;
	IDFT(ta,len);
	for(int i=0;i<ret.size();i++)ret[i]=ta[i];
	return ret;
}
void init(vector<int> A,int op){
	for(auto &i:A)i%=mod;
	sz[op]=A.size();
	for(int j=0;j<=12;j++){
		for(int i=0;i<A.size();i++)tta[op][j][i]=A[i];
		DFT(tta[op][j],4096);
	}
}

}
namespace Conv_104857601{

const int mod=104857601,g=3,invg=((mod+1)%3==0?(mod+1)/3:(2*mod+1)/3);
int wk[4105],ta[4105],tb[4105];
int Power(int x,int y){
	int r=1;
	while(y){
		if(y&1)r=1ll*r*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return r;
}
void DFT(int *a,int n){
	for(int i=n>>1;i;i>>=1){
		int w=Power(g,(mod-1)/(i<<1));
		wk[0]=1;
		for(int j=1;j<i;j++)wk[j]=1ll*wk[j-1]*w%mod;
		for(int j=0;j<n;j+=(i<<1)){
			for(int k=0;k<i;k++){
				int x=a[j+k],y=a[i+j+k],z=x;
				x+=y,(x>=mod&&(x-=mod)),a[j+k]=x;
				z-=y,(z<0&&(z+=mod)),a[i+j+k]=1ll*z*wk[k]%mod;
			}
		}
	}
}
void IDFT(int *a,int n){
	for(int i=1;i<n;i<<=1){
		int w=Power(invg,(mod-1)/(i<<1));
		wk[0]=1;
		for(int j=1;j<i;j++)wk[j]=1ll*wk[j-1]*w%mod;
		for(int j=0;j<n;j+=(i<<1)){
			for(int k=0;k<i;k++){
				int x=a[j+k],y=1ll*a[i+j+k]*wk[k]%mod,z=x;
				x+=y,(x>=mod&&(x-=mod)),a[j+k]=x;
				z-=y,(z<0&&(z+=mod)),a[i+j+k]=z;
			}
		}
	}
	for(int i=0,inv=Power(n,mod-2);i<n;i++)a[i]=1ll*a[i]*inv%mod;
}
int tta[2][15][4105],sz[2];
vector<int> conv(vector<int> A,int op){
	for(auto &i:A)i%=mod;
	int sa=A.size();
	vector<int> ret(sa+sz[op]-1);
	int len=1,o=0;
	while(len<ret.size())len<<=1,o++;
	for(int i=0;i<len;i++)ta[i]=tb[i]=0;
	for(int i=0;i<sa;i++)tb[i]=A[i];
	memcpy(ta,tta[op][o],sizeof(ta));
	DFT(tb,len);
	for(int i=0;i<len;i++)ta[i]=1ll*ta[i]*tb[i]%mod;
	IDFT(ta,len);
	for(int i=0;i<ret.size();i++)ret[i]=ta[i];
	return ret;
}
void init(vector<int> A,int op){
	for(auto &i:A)i%=mod;
	sz[op]=A.size();
	for(int j=0;j<=12;j++){
		for(int i=0;i<A.size();i++)tta[op][j][i]=A[i];
		DFT(tta[op][j],4096);
	}
}

}
const int mod1=998244353,mod2=1004535809,mod3=104857601;
int Power(int x,int y,int mod){
	int r=1;
	while(y){
		if(y&1)r=1ll*r*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return r;
}
void Prework(vector<int> A,int op){
	Conv_998244353::init(A,op);
	Conv_1004535809::init(A,op);
	Conv_104857601::init(A,op);
}
vector<int> conv(vector<int> A,int op){
	__int128 u=1ll*mod2*mod3;
	u*=Power(1ll*mod2*mod3%mod1,mod1-2,mod1);
	
	__int128 v=1ll*mod1*mod3;
	v*=Power(1ll*mod1*mod3%mod2,mod2-2,mod2);
	
	__int128 w=1ll*mod1*mod2;
	w*=Power(1ll*mod1*mod2%mod3,mod3-2,mod3);
	
	__int128 p=1ll*mod1*mod2;
	p*=mod3;
	
	vector<int> v1=Conv_998244353::conv(A,op);
	vector<int> v2=Conv_1004535809::conv(A,op);
	vector<int> v3=Conv_104857601::conv(A,op);
	vector<int> ret(v1.size());
	for(int i=0;i<ret.size();i++){
		ret[i]=((u*v1[i]+v*v2[i]+w*v3[i])%p)%mod;
	}
	return ret;
}
int n,m,a[N+5],f1[N+5],f2[N+5],jc[N+5],ny[N+5];
int C(int x,int y){
	if(x<y||y<0||x<0)return 0;
	return 1ll*jc[x]*ny[y]%mod*ny[x-y]%mod;
}
int Power(int x,int y){
	int r=1;
	while(y){
		if(y&1)r=1ll*r*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return r;
}
int main(){
	jc[0]=ny[0]=1;
	for(int i=1;i<=N;i++)jc[i]=1ll*jc[i-1]*i%mod;
	ny[N]=Power(jc[N],mod-2);
	for(int i=N-1;i;i--)ny[i]=1ll*ny[i+1]*(i+1)%mod;
	scanf("%d%d",&n,&m),f1[0]=1;
	for(int i=1;i<=n*m;i++){
		scanf("%d",&a[i]);
		for(int j=min(i,n);j>=1;j--){
			f1[j]=(f1[j]+1ll*f1[j-1]*a[i])%mod;
		}
	}
	f2[0]=1;
	vector<int> aa(n),bb(n+1);
	for(int i=0;i<n;i++)aa[i]=ny[(i+1)*m-1];
	for(int i=0;i<=n;i++)bb[i]=ny[(i+1)*m-1];
	Prework(aa,0);
	Prework(bb,1);
	int ans=0;
	for(int k=1,d=0;k<=n/2;k++){
		int rem=(m-k%m)%m;
		vector<int> a1(n-d+1);
		for(int i=0;i<=n-d;i++)a1[i]=f2[i+d];
		if(rem!=m-1)d++;
		a1=conv(a1,rem==m-1);
		for(int i=0;i<d;i++)f2[i]=0;
		for(int i=0;i<=n-d;i++)f2[i+d]=a1[i];
		ans=(ans+1ll*f1[k]*f2[(n*m-k)/m]%mod*jc[n*m-k])%mod;
	}
	cout<<ans;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 9ms
memory: 7696kb

input:

3 4
993987920 851664708 532496582 332334976 645105194 437392477 101400616 97233810 821968468 15736516 160047245 366079295

output:

355447772

result:

wrong answer expected 856280467, found 355447772

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 502ms
memory: 7748kb

input:

1500 1
613884366 318223729 617843443 151365784 314748737 778479063 762692152 762329264 560579744 428619194 148701427 891734077 339222910 692588908 180829596 615884679 688697194 981930569 856072945 973079346 407508504 185723413 482150672 944412007 548582506 572572951 297202679 276708377 552007154 951...

output:

522986316

result:

wrong answer expected 716155203, found 522986316

Subtask #3:

score: 0
Wrong Answer

Test #11:

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

input:

100 42
544703372 456304555 178333752 808160596 628160657 264931494 810502429 20342061 203372934 920107110 466566652 470361058 680819469 879463750 668822108 781685938 40434324 800845096 913025163 971899062 986502509 122277391 523016525 579121406 413351231 882719635 632511496 453222515 350376424 37340...

output:

380292457

result:

wrong answer expected 294362854, found 380292457

Subtask #4:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 75ms
memory: 7796kb

input:

499 60
136856769 47869549 264538291 600887500 271130365 503375271 979728502 928286478 295751844 413206031 143796624 712745939 41348750 488666164 725432432 529794914 703056452 573552365 225245406 620490759 715276073 987544150 759181034 939466746 354701446 228245827 301255190 24876250 452483821 837389...

output:

323922011

result:

wrong answer expected 157452172, found 323922011

Subtask #5:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 739ms
memory: 8296kb

input:

1500 93
299567650 399978478 101776752 583392666 56762099 127237968 595272440 581887945 332400603 269986805 17840600 323055242 263161884 607605816 966029729 591250421 964262680 642691696 658567473 339363823 715151825 270553684 202478735 193930303 14517687 248178770 917823665 315265457 473654173 33965...

output:

306776431

result:

wrong answer expected 430115808, found 306776431
English 繁體中文 简体中文

Server Time: 2025-01-21 01:51:13 | OpenSource Project