UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209800#3722. 硬整drdilyor1003300ms65304kbC++111.6kb2024-08-05 09:18:152024-08-05 12:33:44

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
const int mod=998244353;
int fac[2000005],ifac[2000005];
int qkp(int n,int m){
	int res=1;
	while(m){
		if(m&1)(res*=n)%=mod;
		m/=2;
		(n*=n)%=mod;
	}
	return res;
}
int C(int n,int m){
	if(n<0||m<0||n<m)return 0;
	return fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}
int dp[2005][2005];
int pw[2000005];
int n,m;
signed main(){
	fac[0]=1;pw[0]=1;
	for(int i=1;i<=2000000;i++)pw[i]=pw[i-1]*2%mod,fac[i]=fac[i-1]*i%mod;
	ifac[2000000]=qkp(fac[2000000],mod-2);
	for(int i=1999999;i>=0;i--){
		ifac[i]=ifac[i+1]*(i+1)%mod;
	}
	n=read(),m=read();
	dp[0][0]=1;
	int l=2*n;
	//3 6
	//1 4 7
	//2 5 8
	//3 4
	//6 _
	//7 _
	//1 _
	for(int i=1;i<=m;i++){
		int cnt=0;
		for(int j=1;j<=2*n;j++)cnt+=((j%m)==i-1);
		for(int j=(l&1);j<=min(n,l);j+=2){
			if(!dp[i-1][j])continue;
			//把 cnt 个数放入.
			int x=(l-j)/2;
			for(int y=0;y<=j;y++){
				if(y>cnt)continue;
				int p=(cnt-y);
				if(p>x)continue;
				//放 y 个只有 1 对的.
				if(j-y+p<0)continue;
				dp[i][j-y+p]+=dp[i-1][j]*C(x,p)%mod*pw[p]%mod*C(j,y)%mod*fac[p]%mod*fac[y]%mod*C(cnt,y)%mod;
				//cout<<i<<" "<<j<<" "<<y<<" "<<p<<" "<<dp[i-1][j]*C(x,p)%mod*pw[p]%mod*C(j,y)%mod*fac[p]%mod*fac[y]%mod<<"\n";
				dp[i][j-y+p]%=mod;
			}
		}
		l-=cnt;
		//mod m=i-1
		//
	}
	cout<<dp[m][0]<<"\n";
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 23ms
memory: 48052kb

input:

5 4

output:

1428480

result:

ok 1 number(s): "1428480"

Test #2:

score: 0
Accepted
time: 27ms
memory: 48048kb

input:

3 2

output:

288

result:

ok 1 number(s): "288"

Test #3:

score: 0
Accepted
time: 16ms
memory: 48060kb

input:

2 5

output:

24

result:

ok 1 number(s): "24"

Test #4:

score: 0
Accepted
time: 29ms
memory: 48044kb

input:

4 2

output:

9216

result:

ok 1 number(s): "9216"

Test #5:

score: 0
Accepted
time: 31ms
memory: 48052kb

input:

5 4

output:

1428480

result:

ok 1 number(s): "1428480"

Subtask #2:

score: 30
Accepted

Test #6:

score: 30
Accepted
time: 29ms
memory: 48348kb

input:

89 73

output:

559442033

result:

ok 1 number(s): "559442033"

Test #7:

score: 0
Accepted
time: 24ms
memory: 48072kb

input:

93 7

output:

496241225

result:

ok 1 number(s): "496241225"

Test #8:

score: 0
Accepted
time: 15ms
memory: 48036kb

input:

72 1

output:

0

result:

ok 1 number(s): "0"

Test #9:

score: 0
Accepted
time: 30ms
memory: 48320kb

input:

85 66

output:

201689001

result:

ok 1 number(s): "201689001"

Test #10:

score: 0
Accepted
time: 34ms
memory: 48180kb

input:

81 32

output:

790659222

result:

ok 1 number(s): "790659222"

Subtask #3:

score: 10
Accepted

Test #11:

score: 10
Accepted
time: 23ms
memory: 48040kb

input:

96 1

output:

0

result:

ok 1 number(s): "0"

Test #12:

score: 0
Accepted
time: 37ms
memory: 48040kb

input:

79 1

output:

0

result:

ok 1 number(s): "0"

Test #13:

score: 0
Accepted
time: 34ms
memory: 48036kb

input:

82 1

output:

0

result:

ok 1 number(s): "0"

Test #14:

score: 0
Accepted
time: 27ms
memory: 48040kb

input:

73 1

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 33ms
memory: 48040kb

input:

92 1

output:

0

result:

ok 1 number(s): "0"

Subtask #4:

score: 30
Accepted

Test #16:

score: 30
Accepted
time: 195ms
memory: 51524kb

input:

1928 312

output:

850878452

result:

ok 1 number(s): "850878452"

Test #17:

score: 0
Accepted
time: 142ms
memory: 51096kb

input:

1727 287

output:

585132823

result:

ok 1 number(s): "585132823"

Test #18:

score: 0
Accepted
time: 506ms
memory: 65304kb

input:

1615 1751

output:

139736245

result:

ok 1 number(s): "139736245"

Test #19:

score: 0
Accepted
time: 264ms
memory: 52980kb

input:

1751 465

output:

392017200

result:

ok 1 number(s): "392017200"

Test #20:

score: 0
Accepted
time: 94ms
memory: 49696kb

input:

1394 176

output:

183869399

result:

ok 1 number(s): "183869399"

Test #21:

score: 0
Accepted
time: 527ms
memory: 64572kb

input:

1830 1519

output:

218100748

result:

ok 1 number(s): "218100748"

Test #22:

score: 0
Accepted
time: 491ms
memory: 63992kb

input:

1835 1482

output:

371539782

result:

ok 1 number(s): "371539782"

Test #23:

score: 0
Accepted
time: 119ms
memory: 48572kb

input:

1904 48

output:

949353994

result:

ok 1 number(s): "949353994"

Test #24:

score: 0
Accepted
time: 387ms
memory: 57368kb

input:

1758 863

output:

834485506

result:

ok 1 number(s): "834485506"

Test #25:

score: 0
Accepted
time: 163ms
memory: 51208kb

input:

1940 285

output:

726459248

result:

ok 1 number(s): "726459248"

Extra Test:

score: 0
Extra Test Passed