QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#751276 | #9611. 木桶效应 | ANIG | 48 | 2950ms | 26696kb | C++14 | 2.5kb | 2024-11-15 17:51:25 | 2024-11-15 17:51:26 |
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],cnt[M],jc[M],ny[M],bh[N],idx;
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();
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-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;r++){
int sm=0;
for(auto s:zj[t]){
int tmp=pows(n-i-(j-l)-r-(cnt[k]-cnt[t])-cnt[s],m-sz);
for(int u=0;u<sz;u++){
int sm=n-i-(j-l)-r-(cnt[k]-cnt[t])-cnt[s],op=0;
for(auto d:dy[u]){
if((s>>bh[g[d].y]-1&1^1)&&((k^t)>>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^t)>>op-1&1)sm=0;
else if(s>>op-1&1)sm=0;
else sm=1;
}
// cout<<i<<" "<<j<<" "<<k<<" "<<l<<" "<<t<<" "<<s<<" "<<tmp<<" "<<u<<" "<<sm<<" "<<op<<endl;
tmp=tmp*sm%mods;
}
// cout<<i<<" "<<j<<" "<<k<<" "<<l<<" "<<t<<" "<<s<<" "<<tmp<<endl;
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;
}
详细
Subtask #1:
score: 4
Accepted
Test #1:
score: 4
Accepted
time: 1ms
memory: 5700kb
input:
5 3 0
output:
21412920
result:
ok single line: '21412920'
Test #2:
score: 4
Accepted
time: 0ms
memory: 5932kb
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: 5708kb
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: 1ms
memory: 5788kb
input:
7 3 0
output:
160221085
result:
ok single line: '160221085'
Test #5:
score: 8
Accepted
time: 1ms
memory: 5732kb
input:
7 3 2 1 1 5 1 6 2
output:
598007855
result:
ok single line: '598007855'
Test #6:
score: 8
Accepted
time: 1ms
memory: 7684kb
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: 8ms
memory: 26696kb
input:
50 1 0
output:
263941435
result:
ok single line: '263941435'
Test #8:
score: 8
Accepted
time: 8ms
memory: 22308kb
input:
43 2 0
output:
136378346
result:
ok single line: '136378346'
Test #9:
score: 8
Accepted
time: 13ms
memory: 26192kb
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: 190ms
memory: 25056kb
input:
50 292247015 0
output:
226872193
result:
ok single line: '226872193'
Test #11:
score: 12
Accepted
time: 159ms
memory: 26100kb
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: 2950ms
memory: 13872kb
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: 2607ms
memory: 11912kb
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: 2940ms
memory: 14148kb
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: 266ms
memory: 12084kb
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: 783ms
memory: 13888kb
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: 0
Time Limit Exceeded
Dependency #5:
100%
Accepted
Test #17:
score: 0
Time Limit Exceeded
input:
50 915702052 5 541920465 39 16 833447607 49 14 326677362 14 34 412319566 10 36 206682128 46 28
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #7:
0%
Subtask #9:
score: 0
Skipped
Dependency #8:
0%