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