UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209806#3722. 硬整drdilyor1001478ms65304kbC++111.3kb2024-08-05 09:21:472024-08-05 12:34:02

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;
	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;
			int x=(l-j)/2;
			for(int y=max(0ll,cnt-x);y<=min(j,cnt);y++){
				int p=(cnt-y);
				dp[i][j-y+p]+=dp[i-1][j]*C(x,p)%mod*pw[p]%mod*C(j,y)%mod*fac[cnt]%mod;
				if(dp[i][j-y+p]>=mod)dp[i][j-y+p]-=mod;
			}
		}
		l-=cnt;
	}
	cout<<dp[m][0]<<"\n";
	return 0;
}

详细

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

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 20ms
memory: 48056kb

input:

5 4

output:

1428480

result:

ok 1 number(s): "1428480"

Test #2:

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

input:

3 2

output:

288

result:

ok 1 number(s): "288"

Test #3:

score: 0
Accepted
time: 35ms
memory: 48056kb

input:

2 5

output:

24

result:

ok 1 number(s): "24"

Test #4:

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

input:

4 2

output:

9216

result:

ok 1 number(s): "9216"

Test #5:

score: 0
Accepted
time: 21ms
memory: 48056kb

input:

5 4

output:

1428480

result:

ok 1 number(s): "1428480"

Subtask #2:

score: 30
Accepted

Test #6:

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

input:

89 73

output:

559442033

result:

ok 1 number(s): "559442033"

Test #7:

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

input:

93 7

output:

496241225

result:

ok 1 number(s): "496241225"

Test #8:

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

input:

72 1

output:

0

result:

ok 1 number(s): "0"

Test #9:

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

input:

85 66

output:

201689001

result:

ok 1 number(s): "201689001"

Test #10:

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

input:

81 32

output:

790659222

result:

ok 1 number(s): "790659222"

Subtask #3:

score: 10
Accepted

Test #11:

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

input:

96 1

output:

0

result:

ok 1 number(s): "0"

Test #12:

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

input:

79 1

output:

0

result:

ok 1 number(s): "0"

Test #13:

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

input:

82 1

output:

0

result:

ok 1 number(s): "0"

Test #14:

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

input:

73 1

output:

0

result:

ok 1 number(s): "0"

Test #15:

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

input:

92 1

output:

0

result:

ok 1 number(s): "0"

Subtask #4:

score: 30
Accepted

Test #16:

score: 30
Accepted
time: 77ms
memory: 51520kb

input:

1928 312

output:

850878452

result:

ok 1 number(s): "850878452"

Test #17:

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

input:

1727 287

output:

585132823

result:

ok 1 number(s): "585132823"

Test #18:

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

input:

1615 1751

output:

139736245

result:

ok 1 number(s): "139736245"

Test #19:

score: 0
Accepted
time: 97ms
memory: 52976kb

input:

1751 465

output:

392017200

result:

ok 1 number(s): "392017200"

Test #20:

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

input:

1394 176

output:

183869399

result:

ok 1 number(s): "183869399"

Test #21:

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

input:

1830 1519

output:

218100748

result:

ok 1 number(s): "218100748"

Test #22:

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

input:

1835 1482

output:

371539782

result:

ok 1 number(s): "371539782"

Test #23:

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

input:

1904 48

output:

949353994

result:

ok 1 number(s): "949353994"

Test #24:

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

input:

1758 863

output:

834485506

result:

ok 1 number(s): "834485506"

Test #25:

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

input:

1940 285

output:

726459248

result:

ok 1 number(s): "726459248"

Extra Test:

score: 0
Extra Test Passed