QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#73650 | #4811. Be Careful | CharlieVinnie | WA | 3ms | 5688kb | C++20 | 2.8kb | 2023-01-27 13:26:25 | 2023-01-27 13:26:26 |
Judging History
answer
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std;
const int N=205,mod=998244353; typedef long long ll;
int n,C[N][N],f[N][N],sf[N][N],deg[N],cnt[N],g[1<<22],h[1<<22][23]; vector<int> to[N];
inline int ID(int x) { return x?mod-1:1; }
void dfs(int u,int pa){
if(to[u].size()==1u&&pa!=0) { deg[u]=0; For(i,0,n) f[u][i]=1,sf[u][i]=n-i+1; ; return; }
for(int v:to[u]) if(v!=pa) dfs(v,u),deg[u]++;
memset(cnt,0,sizeof(cnt)); for(int v:to[u]) if(v!=pa) cnt[deg[v]]++; ; For(i,1,n) cnt[i]+=cnt[i-1];
int B=0,ww=1e9; For(i,0,21) if(i+cnt[n]-cnt[i]<ww) ww=i+cnt[n]-cnt[i],B=i;
vector<int> lis; for(int v:to[u]) if(v!=pa&°[v]>B) lis.push_back(v); ; int sz=lis.size();
int lfcnt=0; for(int v:to[u]) if(v!=pa&&!deg[v]) lfcnt++;
// cerr<<"u="<<u<<": B="<<B<<" sz="<<sz<<endl;
assert(B<22&&sz<=22);
const int all=(1<<(B+1))-1; For(s,0,all){
g[s]=1; for(int v:to[u]) if(v!=pa&°[v]<=B&°[v]){
int cc=0; For(i,0,B) if(!((s>>i)&1)) cc=(cc+f[v][i])%mod; ; g[s]=1ll*g[s]*cc%mod;
}
}
For(s,0,all) for(int s0=all^s;s0;s0=(s0-1)&(all^s)) g[s]=(g[s]+1ll*ID(s0)*g[s|s0])%mod;
// For(s,0,all) cerr<<g[s]<<' '; ; cerr<<endl;
const int all2=(1<<sz)-1;
For(ss,0,all) if(g[ss]) {
For(s,0,all2) For(j,0,lfcnt) h[s][j]=0; ; h[0][0]=g[ss];
For(i,0,n){
if(i>B||(i<=B&&((ss>>i)&1))){
For(s,0,all2) For(j,0,lfcnt) if(h[s][j]){
int w=h[s][j]; For(t,0,sz-1) if(!((s>>t)&1)) w=1ll*w*sf[lis[t]][i+1]%mod;
For(_,1,lfcnt-j) w=1ll*w*(n-i)%mod;
// printf("ss=%d,s=%d: f[%d][%d]+=%d\n",ss,s,u,i,w);
f[u][i]=(f[u][i]+w)%mod;
}
}
Rev(s,all2,0) Rev(j,lfcnt,0) if(h[s][j]){
for(int s0=all2^s;;s0=(s0-1)&(all2^s)){
int w=h[s][j]; For(t,0,sz-1) if((s0>>t)&1) w=1ll*w*f[lis[t]][i]%mod;
For(k,j+(s0==0),lfcnt) h[s|s0][k]=(h[s|s0][k]+1ll*w*C[lfcnt-j][lfcnt-k])%mod;
if(!s0) break;
}
h[s][j]=0;
}
}
}
Rev(i,n,0) sf[u][i]=(sf[u][i+1]+f[u][i])%mod;
}
signed main(){
cin>>n; For(i,1,n-1) { int x,y; cin>>x>>y; to[x].push_back(y); to[y].push_back(x); }
C[0][0]=1; For(i,1,n) { C[i][0]=1; For(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; } ; dfs(1,0);
// For(u,1,n){
// For(i,0,n) cerr<<f[u][i]<<' '; ; cerr<<endl;
// }
For(i,0,n) cout<<f[1][i]<<'\n';
cerr<<"Time = "<<clock()<<" ms\n";
return 0;
}
// START TYPING IF YOU DON'T KNOW WHAT TO DO
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5576kb
input:
5 1 2 1 3 2 4 2 5
output:
55 127 34 0 0 0
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 5656kb
input:
8 1 2 1 3 1 4 1 5 1 6 6 7 6 8
output:
69632 265534 133905 47790 12636 1944 0 0 0
result:
ok 9 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 5580kb
input:
3 1 2 2 3
output:
1 3 0 0
result:
ok 4 number(s): "1 3 0 0"
Test #4:
score: 0
Accepted
time: 3ms
memory: 5512kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 5512kb
input:
10 1 8 1 9 6 1 2 1 1 4 1 10 1 5 7 1 3 1
output:
1755647 612579511 359376750 200038110 104287680 49974120 21379680 7771680 2177280 362880 0
result:
ok 11 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 5660kb
input:
10 2 8 2 9 6 2 2 1 2 4 2 10 2 5 7 2 3 2
output:
114358881 100000000 0 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #7:
score: 0
Accepted
time: 3ms
memory: 5556kb
input:
10 7 8 8 9 6 5 2 1 3 4 9 10 4 5 7 6 3 2
output:
10 1 0 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 5560kb
input:
10 3 6 2 4 4 9 8 4 2 5 10 5 3 7 2 1 1 3
output:
27510 31142 102399 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #9:
score: 0
Accepted
time: 3ms
memory: 5640kb
input:
14 10 3 6 2 2 8 3 13 1 3 1 2 3 14 4 2 9 3 12 3 2 5 7 2 11 3
output:
930962871 780146137 253920328 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 15 numbers
Test #10:
score: 0
Accepted
time: 2ms
memory: 5688kb
input:
20 7 6 2 6 5 1 17 12 9 13 12 18 3 2 9 1 2 1 12 6 10 9 14 2 4 1 6 8 11 2 16 9 13 19 8 15 20 5
output:
572808214 694156482 763085092 958730326 465749894 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 21 numbers
Test #11:
score: -100
Wrong Answer
time: 3ms
memory: 5548kb
input:
21 6 12 11 13 1 7 8 14 1 18 5 4 1 2 16 11 21 1 9 10 15 17 1 9 1 8 1 20 1 3 1 4 19 16 11 1 15 10 3 6
output:
778184256 122063995 235822069 404617965 15600991 959138046 628411891 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
wrong answer 2nd numbers differ - expected: '242901486', found: '122063995'