QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#751294 | #9611. 木桶效应 | ANIG | 60 | 1272ms | 141424kb | C++14 | 2.5kb | 2024-11-15 17:59:14 | 2024-11-15 17:59:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=55,M=(1<<10)+5,mods=998244353;
int pows(int a,int b){
if(b==0)return 1;
int res=pows(a,b>>1);
res=res*res%mods;
if(b&1)res=res*a%mods;
return res;
}
struct node{
int x,y,w;
}g[N];
int n,m,qs,sz,f[N][N][M],pw[N],cnt[M],jc[M],ny[M],bh[N],idx,dp[N][M][M];
vector<int>zj[M],dy[N];
int C(int a,int b){
if(a<0||b<0||a<b)return 0;
return jc[a]*ny[b]%mods*ny[a-b]%mods;
}
signed main(){
vector<int>jl;
auto fd=[&](int x){
return lower_bound(jl.begin(),jl.end(),x)-jl.begin();
};
cin>>n>>m>>qs;
for(int i=1;i<=qs;i++){
cin>>g[i].x>>g[i].y>>g[i].w;
if(!bh[g[i].y])bh[g[i].y]=++idx;
jl.push_back(g[i].x);
}
for(int i=0;i<(1<<idx);i++){
for(int j=i;j;j=j-1&i)zj[i].push_back(j);
zj[i].push_back(0);
cnt[i]=__builtin_popcount(i);
}
sort(jl.begin(),jl.end());
jl.resize(unique(jl.begin(),jl.end())-jl.begin());
for(int i=1;i<=qs;i++)dy[fd(g[i].x)].push_back(i);
sz=jl.size();
for(int i=0;i<=n;i++)pw[i]=pows(i,m-sz);
jc[0]=ny[0]=1;
for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i%mods,ny[i]=pows(jc[i],mods-2);
f[0][n-idx][(1<<idx)-1]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<(1<<idx);k++){
for(auto s:zj[k^(1<<idx)-1]){
int tmp=pw[j-cnt[k]-cnt[s]];
for(int u=0;u<sz;u++){
int sm=j-cnt[k]-cnt[s],op=0;
for(auto d:dy[u]){
if((s>>bh[g[d].y]-1&1^1)&&(k>>bh[g[d].y]-1&1^1)&&g[d].w>i+1)sm--;
if(g[d].w==i+1)op=bh[g[d].y];
}
if(op){
if(k>>op-1&1)sm=0;
else if(s>>op-1&1)sm=0;
else sm=1;
}
tmp=tmp*sm%mods;
}
dp[j][k][s]=tmp;
}
}
}
for(int j=0;j<=n-idx;j++){
for(int k=0;k<(1<<idx);k++){
for(int l=0;l<=j;l++){
for(auto t:zj[k]){
int ans=0;
for(int r=0;r<=l&&n-i-(j-l)-r>=0;r++){
int sm=0;
for(auto s:zj[t]){
int tmp=dp[n-i-(j-l)-r][k^t][s];
if(cnt[s]&1)sm-=tmp;
else sm+=tmp;
}
sm%=mods;
if(r&1)ans-=sm*C(l,r)%mods;
else ans+=sm*C(l,r)%mods;
}
ans%=mods;
f[i+1][j-l][k^t]+=f[i][j][k]*ans%mods*pows(i+1,l+cnt[t])%mods*C(j,l)%mods;
}
}
}
}
for(int j=0;j<=n-idx;j++){
for(int k=0;k<(1<<idx);k++){
f[i+1][j][k]%=mods;
// cout<<i+1<<" "<<j<<" "<<k<<" "<<f[i+1][j][k]<<endl;
}
}
}
cout<<(f[n][0][0]+mods)%mods;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 4
Accepted
Test #1:
score: 4
Accepted
time: 0ms
memory: 15880kb
input:
5 3 0
output:
21412920
result:
ok single line: '21412920'
Test #2:
score: 4
Accepted
time: 0ms
memory: 16136kb
input:
5 3 2 3 4 4 2 5 3
output:
847674
result:
ok single line: '847674'
Test #3:
score: 4
Accepted
time: 2ms
memory: 15944kb
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: 22304kb
input:
7 3 0
output:
160221085
result:
ok single line: '160221085'
Test #5:
score: 8
Accepted
time: 2ms
memory: 20044kb
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: 20100kb
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: 7ms
memory: 128556kb
input:
50 1 0
output:
263941435
result:
ok single line: '263941435'
Test #8:
score: 8
Accepted
time: 4ms
memory: 110396kb
input:
43 2 0
output:
136378346
result:
ok single line: '136378346'
Test #9:
score: 8
Accepted
time: 7ms
memory: 129296kb
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: 3ms
memory: 128532kb
input:
50 292247015 0
output:
226872193
result:
ok single line: '226872193'
Test #11:
score: 12
Accepted
time: 8ms
memory: 128948kb
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: 26ms
memory: 61008kb
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: 33ms
memory: 59140kb
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: 33ms
memory: 59276kb
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: 6ms
memory: 52956kb
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: 17ms
memory: 53072kb
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: 1272ms
memory: 140940kb
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: 1269ms
memory: 141264kb
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: 1252ms
memory: 141424kb
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: 130ms
memory: 130564kb
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: 408ms
memory: 135352kb
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: 0
Time Limit Exceeded
Dependency #6:
100%
Accepted
Test #22:
score: 0
Time Limit Exceeded
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:
result:
Subtask #8:
score: 0
Skipped
Dependency #7:
0%
Subtask #9:
score: 0
Skipped
Dependency #8:
0%