QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#718195 | #9611. 木桶效应 | Nesraychan | 100 ✓ | 242ms | 4380kb | C++14 | 2.5kb | 2024-11-06 19:56:16 | 2024-11-06 19:56:18 |
Judging History
answer
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 55
#define M (1<<10|5)
#define mod 998244353
IL int read()
{
reg int x=0,f=0; reg char ch=getchar();
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
IL int Add(reg int x,reg int y){return x+y<mod?x+y:x+y-mod;}
IL void Pls(reg int &x,reg int y){x=Add(x,y);}
IL int Mul(reg int x,reg int y){long long r=1ll*x*y; return r<mod?r:r%mod;}
IL int power(reg int x,reg int p){reg int r=1; for(;p;p>>=1,x=Mul(x,x))if(p&1)r=Mul(r,x); return r;}
int n,m,q,mn[N];
IL void cmin(reg int &x,reg int y){x>y?x=y:0;}
int f[N][M],nf[N][M],con[N],binom[N][N],pop[M];
bool col[N];
int p[N],tot,cnt,full;
std::map<int,int>id;
std::vector<std::pair<int,int>>vec[N];
main()
{
n=read(),m=read(),q=read();
for(reg int i=1;i<=n;++i)mn[i]=n;
for(reg int x,y,k;q--;)
{
x=read(),y=read(),k=read();
cmin(mn[y],k),col[y]=1;
if(!id.count(x))id[x]=++cnt;
vec[y].push_back({id[x],k});
}
for(reg int i=1;i<=n;++i)if(col[i])p[tot++]=i;
full=1<<tot;
for(reg int s=1;s<full;++s)pop[s]=pop[s>>1]+(s&1);
for(reg int i=0;i<=n;++i)con[i]=power(i,m-cnt);
for(reg int i=0;i<=n;++i)binom[i][0]=1;
for(reg int i=1,j;i<=n;++i)for(j=1;j<=i;++j)
binom[i][j]=Add(binom[i-1][j],binom[i-1][j-1]);
f[0][0]=1;
for(reg int i=n,s,j,k,w,o;i;--i)
{
for(j=0;j<=n;++j)for(s=full;s--;)if(w=f[j][s])
{
reg int x=n-j,y=i-1;
if(m>cnt)
{
if(x>=y)w=Mul(w,con[x-y]);
else w=0;
}
static int val[N];
for(k=1;k<=cnt;++k)val[k]=x-y;
for(o=tot;o--;)if(~s>>o&1)
for(auto &[row,t]:vec[p[o]])
if(t>i)--val[row];
for(o=tot;o--;)if(~s>>o&1)
for(auto &[row,t]:vec[p[o]])
if(t==i)val[row]=1;
for(k=1;k<=cnt&&w;++k)
if(val[k]>0)w=Mul(w,val[k]);
else w=0;
f[j][s]=w;
}
for(o=tot;o--;)if(mn[p[o]]>=i)for(s=full;s--;)if(~s>>o&1)
for(j=0;j<=n;++j)if(w=f[j][s])Pls(f[j+1][s|(1<<o)],w);
for(j=0;j<=n;++j)for(s=full;s--;)if(w=f[j][s])for(k=0;j+k<=n;++k)
Pls(nf[j+k][s],Mul(w,binom[n-tot-j+pop[s]][k]));
for(j=0;j<=n;++j)for(s=full;s--;)f[j][s]=nf[j][s],nf[j][s]=0;
}
printf("%d\n",f[n][full-1]);
}
詳細信息
Subtask #1:
score: 4
Accepted
Test #1:
score: 4
Accepted
time: 0ms
memory: 3808kb
input:
5 3 0
output:
21412920
result:
ok single line: '21412920'
Test #2:
score: 4
Accepted
time: 0ms
memory: 3852kb
input:
5 3 2 3 4 4 2 5 3
output:
847674
result:
ok single line: '847674'
Test #3:
score: 4
Accepted
time: 0ms
memory: 4004kb
input:
5 3 3 3 5 5 1 2 5 2 5 3
output:
168780
result:
ok single line: '168780'
Subtask #2:
score: 8
Accepted
Dependency #1:
100%
Accepted
Test #4:
score: 8
Accepted
time: 0ms
memory: 3876kb
input:
7 3 0
output:
160221085
result:
ok single line: '160221085'
Test #5:
score: 8
Accepted
time: 0ms
memory: 3796kb
input:
7 3 2 1 1 5 1 6 2
output:
598007855
result:
ok single line: '598007855'
Test #6:
score: 8
Accepted
time: 0ms
memory: 3872kb
input:
7 3 3 1 1 5 2 6 3 2 1 7
output:
950880222
result:
ok single line: '950880222'
Subtask #3:
score: 8
Accepted
Test #7:
score: 8
Accepted
time: 1ms
memory: 4172kb
input:
50 1 0
output:
263941435
result:
ok single line: '263941435'
Test #8:
score: 8
Accepted
time: 0ms
memory: 4320kb
input:
43 2 0
output:
136378346
result:
ok single line: '136378346'
Test #9:
score: 8
Accepted
time: 1ms
memory: 4180kb
input:
50 2 0
output:
489087596
result:
ok single line: '489087596'
Subtask #4:
score: 12
Accepted
Dependency #3:
100%
Accepted
Test #10:
score: 12
Accepted
time: 1ms
memory: 4152kb
input:
50 292247015 0
output:
226872193
result:
ok single line: '226872193'
Test #11:
score: 12
Accepted
time: 1ms
memory: 4248kb
input:
50 873009728 0
output:
63648791
result:
ok single line: '63648791'
Subtask #5:
score: 16
Accepted
Dependency #2:
100%
Accepted
Dependency #4:
100%
Accepted
Test #12:
score: 16
Accepted
time: 0ms
memory: 4000kb
input:
20 728836785 5 248289571 15 16 439110385 8 15 339467267 12 7 585491339 7 9 605518440 4 1
output:
761275883
result:
ok single line: '761275883'
Test #13:
score: 16
Accepted
time: 0ms
memory: 3996kb
input:
20 288197925 5 31379347 9 1 222153278 1 1 24531748 20 1 106427339 18 1 212338331 17 1
output:
877851586
result:
ok single line: '877851586'
Test #14:
score: 16
Accepted
time: 1ms
memory: 3992kb
input:
20 880439688 5 563540321 17 20 395236367 3 20 300712779 6 20 121406689 18 20 25890496 9 20
output:
186649553
result:
ok single line: '186649553'
Test #15:
score: 16
Accepted
time: 1ms
memory: 3920kb
input:
20 311402369 5 311293636 14 13 306211116 19 19 36858994 5 11 36858994 19 10 306211116 14 18
output:
415461922
result:
ok single line: '415461922'
Test #16:
score: 16
Accepted
time: 1ms
memory: 3916kb
input:
20 98953332 5 1075868 12 5 31161114 8 12 46790018 9 10 39214697 15 7 46790018 8 8
output:
204149614
result:
ok single line: '204149614'
Subtask #6:
score: 12
Accepted
Dependency #5:
100%
Accepted
Test #17:
score: 12
Accepted
time: 3ms
memory: 4156kb
input:
50 915702052 5 541920465 39 16 833447607 49 14 326677362 14 34 412319566 10 36 206682128 46 28
output:
783441394
result:
ok single line: '783441394'
Test #18:
score: 12
Accepted
time: 1ms
memory: 4380kb
input:
50 47879239 5 30666754 20 1 23945845 17 1 27229141 25 1 40551703 9 1 15723198 18 1
output:
546399382
result:
ok single line: '546399382'
Test #19:
score: 12
Accepted
time: 5ms
memory: 4152kb
input:
50 334191703 5 167838076 19 50 95127599 33 50 221030062 4 50 89223523 36 50 40736662 39 50
output:
242104112
result:
ok single line: '242104112'
Test #20:
score: 12
Accepted
time: 1ms
memory: 4156kb
input:
50 33538004 5 1341436 40 26 19132404 4 13 22271562 24 25 19132404 40 18 19132404 24 38
output:
509216038
result:
ok single line: '509216038'
Test #21:
score: 12
Accepted
time: 2ms
memory: 4148kb
input:
50 453197583 5 304895210 17 41 450727109 33 20 129855576 4 24 214262208 12 46 214262208 4 27
output:
929330226
result:
ok single line: '929330226'
Subtask #7:
score: 20
Accepted
Dependency #6:
100%
Accepted
Test #22:
score: 20
Accepted
time: 14ms
memory: 4176kb
input:
50 733592974 7 204969642 20 32 532101473 38 22 428067108 29 19 699479674 23 35 403248947 11 33 523610998 39 50 207894041 37 47
output:
878602112
result:
ok single line: '878602112'
Test #23:
score: 20
Accepted
time: 2ms
memory: 4220kb
input:
50 363989184 7 275675456 32 1 14440487 41 1 84675645 18 1 112753584 7 1 259289962 30 1 244964889 42 1 34667760 27 1
output:
125183718
result:
ok single line: '125183718'
Test #24:
score: 20
Accepted
time: 22ms
memory: 4252kb
input:
50 987882639 7 17913003 22 50 440453368 26 50 849090802 8 50 106136773 13 50 491841612 34 50 131376512 15 50 231961452 39 50
output:
573542486
result:
ok single line: '573542486'
Test #25:
score: 20
Accepted
time: 1ms
memory: 4244kb
input:
50 739368354 7 163377222 20 27 192827369 29 10 688310083 50 13 20398047 27 45 688310083 29 11 192827369 20 5 688310083 27 27
output:
528550901
result:
ok single line: '528550901'
Test #26:
score: 20
Accepted
time: 2ms
memory: 4160kb
input:
50 691852384 7 552436456 27 11 103126750 8 13 122888842 49 34 306609066 7 11 553011271 38 32 553011271 27 47 553011271 49 50
output:
407673475
result:
ok single line: '407673475'
Test #27:
score: 20
Accepted
time: 4ms
memory: 4168kb
input:
50 828246844 7 528561184 35 4 15522388 43 35 679004541 17 20 161133582 6 20 289045078 32 49 705209075 24 38 705209075 17 44
output:
734432988
result:
ok single line: '734432988'
Subtask #8:
score: 12
Accepted
Dependency #7:
100%
Accepted
Test #28:
score: 12
Accepted
time: 51ms
memory: 4228kb
input:
50 818455715 9 460012830 5 33 118588510 47 47 281020207 23 25 175303600 1 18 234157803 48 32 256460906 19 46 287657461 24 13 81772046 14 22 114821805 44 41
output:
863394340
result:
ok single line: '863394340'
Test #29:
score: 12
Accepted
time: 4ms
memory: 4316kb
input:
50 24969517 9 23565097 13 1 11005666 43 1 21727790 47 1 12763778 6 1 6881701 34 1 2985794 23 1 13971040 15 1 13187518 29 1 1995154 12 1
output:
755357189
result:
ok single line: '755357189'
Test #30:
score: 12
Accepted
time: 111ms
memory: 4232kb
input:
50 429772980 9 414497820 4 50 141139445 19 50 407732495 7 50 83785413 1 50 164351908 8 50 213988430 26 50 52240611 50 50 352159955 27 50 279326344 29 50
output:
247413078
result:
ok single line: '247413078'
Test #31:
score: 12
Accepted
time: 4ms
memory: 4224kb
input:
50 919810726 9 403069670 48 3 193931638 39 28 821686776 22 11 432351038 8 49 466123383 14 34 254851369 2 48 193931638 48 38 821686776 8 19 254851369 8 20
output:
481094724
result:
ok single line: '481094724'
Test #32:
score: 12
Accepted
time: 3ms
memory: 4236kb
input:
50 619619808 9 140356219 25 31 289966305 18 15 308904151 23 44 530131662 15 2 174186843 35 5 452736627 42 7 12231110 21 2 308904151 18 33 140356219 18 30
output:
194056785
result:
ok single line: '194056785'
Test #33:
score: 12
Accepted
time: 3ms
memory: 4192kb
input:
50 405638475 9 189173757 25 33 313860932 22 8 196599730 26 6 273814431 3 2 52701532 15 14 335951766 19 3 313077524 29 13 349363426 7 15 313860932 19 19
output:
435209021
result:
ok single line: '435209021'
Subtask #9:
score: 8
Accepted
Dependency #8:
100%
Accepted
Test #34:
score: 8
Accepted
time: 50ms
memory: 4380kb
input:
50 946059042 10 160844820 11 40 246397981 49 28 373026730 1 18 602144414 9 9 284028279 39 44 22155194 16 2 851925494 6 17 862159117 27 32 773018252 10 20 462257810 48 19
output:
680391855
result:
ok single line: '680391855'
Test #35:
score: 8
Accepted
time: 3ms
memory: 4188kb
input:
50 260661857 10 70899239 47 1 248286199 34 1 49459370 23 1 110741847 3 1 13147285 19 1 75609139 10 1 16001621 49 1 258636033 17 1 41404092 36 1 259336018 9 1
output:
621578303
result:
ok single line: '621578303'
Test #36:
score: 8
Accepted
time: 242ms
memory: 4180kb
input:
50 444766827 10 138606634 2 50 356874907 48 50 186818234 44 50 328471606 8 50 57922803 45 50 442175507 50 50 45412871 41 50 111164719 24 50 278665393 39 50 49548102 15 50
output:
476500313
result:
ok single line: '476500313'
Test #37:
score: 8
Accepted
time: 2ms
memory: 4164kb
input:
50 471185620 10 330350191 32 46 19091103 17 9 383913632 38 25 125638511 4 13 227803510 12 49 140314389 27 34 97824926 22 46 19091103 27 16 140314389 38 4 97824926 12 1
output:
746959227
result:
ok single line: '746959227'
Test #38:
score: 8
Accepted
time: 17ms
memory: 4232kb
input:
50 534235345 10 505481965 11 39 325061903 12 35 443938537 40 20 144968487 29 31 292692014 18 39 423914803 14 36 221863124 46 41 413488879 5 39 413488879 14 5 325061903 11 42
output:
83413094
result:
ok single line: '83413094'
Test #39:
score: 8
Accepted
time: 26ms
memory: 4260kb
input:
50 268783055 10 164040236 5 3 77416439 15 8 215664484 32 34 84807773 8 44 242418459 20 43 132116147 31 13 11369559 50 23 264864429 6 42 153908131 3 27 132116147 20 50
output:
858392519
result:
ok single line: '858392519'
Test #40:
score: 8
Accepted
time: 0ms
memory: 4224kb
input:
50 680178330 10 381317639 8 3 97592656 22 6 66456445 4 9 277935856 2 13 629083753 35 33 86588466 7 25 86588466 8 6 66456445 22 11 97592656 8 23 277935856 7 24
output:
274256402
result:
ok single line: '274256402'