ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#209806 | #3722. 硬整 | drdilyor | 100 | 1478ms | 65304kb | C++11 | 1.3kb | 2024-08-05 09:21:47 | 2024-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