QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#73650#4811. Be CarefulCharlieVinnieWA 3ms5688kbC++202.8kb2023-01-27 13:26:252023-01-27 13:26:26

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-27 13:26:26]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:5688kb
  • [2023-01-27 13:26:25]
  • 提交

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&&deg[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&&deg[v]<=B&&deg[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

Details

Tip: Click on the bar to expand more detailed information

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'