QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#73693	#4811. Be Careful	CharlieVinnie	TL	694ms	33728kb	C++20	2.8kb	2023-01-27 16:29:35	2023-01-27 16:29:38

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 16:29:38]
评测

测评结果：TL
用时：694ms
内存：33728kb

查看

[2023-01-27 16:29:35]
提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#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,A=18,mod=998244353; typedef long long ll;
int n,C[N][N],f[N][N],sf[N][N],deg[N],cnt[N],g[1<<A],h[1<<A][N],tmp[1<<A][N],pw[N][N]; vector<int> to[N];
inline int ID(int x) { return (x&1)?mod-1:1; }
inline void qmo(int& x) { x+=(x>>31)&mod; }
inline bool ckmin(int& x,int y) { if(x>y) return x=y,true; else return false; }
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 lfcnt=0; for(int v:to[u]) if(v!=pa&&!deg[v]) lfcnt++;
    int B=0,ww=1e9; For(i,0,n) if(i<A&&cnt[n]-cnt[i]<=A&&ckmin(ww,pow(2,i)*i+pow(2,i+cnt[n]-cnt[i])*deg[u]*lfcnt)) B=i;
    vector<int> lis; for(int v:to[u]) if(v!=pa&&deg[v]>B) lis.push_back(v); ; int sz=lis.size();
    assert(B<A&&sz<=A);
    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)) qmo(cc+=f[v][i]-mod); ; g[s]=1ll*g[s]*cc%mod;
        }
    }
    For(i,0,B) For(s,0,all) if(!((s>>i)&1)) g[s]=(g[s]+1ll*(mod-1)*g[s|(1<<i)])%mod;
    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,deg[u]){
            if(i>B||(i<=B&&((ss>>i)&1))){
                For(s,0,all2) For(j,0,lfcnt) if(h[s][j]){
                    int w=1ll*h[s][j]*pw[n-i][lfcnt-j]%mod; For(t,0,sz-1) if(!((s>>t)&1)) w=1ll*w*sf[lis[t]][i+1]%mod;
                    qmo(f[u][i]+=w-mod);
                }
            }
            For(s,0,all2) For(j,0,lfcnt) tmp[s][j]=h[s][j];
            For(s,0,all2) Rev(j,lfcnt,0) if(h[s][j]) For(k,j+1,lfcnt) h[s][k]=(h[s][k]+1ll*h[s][j]*C[lfcnt-j][lfcnt-k])%mod;
            For(j,0,lfcnt) For(k,0,sz-1) For(s,0,all2) if(!((s>>k)&1)) h[s|(1<<k)][j]=(h[s|(1<<k)][j]+1ll*h[s][j]*f[lis[k]][i])%mod;
            if(i>B||((ss>>i)&1)) For(s,0,all2) For(j,0,lfcnt) qmo(h[s][j]-=tmp[s][j]);
        }
    }
    Rev(i,n,0) sf[u][i]=(sf[u][i+1]+f[u][i])%mod;
}
signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    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; }
    For(i,1,n) { pw[i][0]=1; For(j,1,n) pw[i][j]=1ll*pw[i][j-1]*i%mod; }
    dfs(1,0); 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

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 3ms

memory: 7780kb

input:

output:

result:

ok 6 numbers

Test #2:

score: 0

Accepted

time: 3ms

memory: 7792kb

input:

output:

result:

ok 9 numbers

Test #3:

score: 0

Accepted

time: 0ms

memory: 7728kb

input:

3
1 2
2 3

output:

result:

ok 4 number(s): "1 3 0 0"

Test #4:

score: 0

Accepted

time: 3ms

memory: 7756kb

input:

2
1 2

output:

2
1
0

result:

ok 3 number(s): "2 1 0"

Test #5:

score: 0

Accepted

time: 0ms

memory: 7580kb

input:

output:

result:

ok 11 numbers

Test #6:

score: 0

Accepted

time: 2ms

memory: 7792kb

input:

output:

result:

ok 11 numbers

Test #7:

score: 0

Accepted

time: 0ms

memory: 7660kb

input:

output:

result:

ok 11 numbers

Test #8:

score: 0

Accepted

time: 0ms

memory: 7824kb

input:

output:

result:

ok 11 numbers

Test #9:

score: 0

Accepted

time: 3ms

memory: 7812kb

input:

output:

result:

ok 15 numbers

Test #10:

score: 0

Accepted

time: 3ms

memory: 7812kb

input:

output:

result:

ok 21 numbers

Test #11:

score: 0

Accepted

time: 3ms

memory: 7864kb

input:

output:

result:

ok 22 numbers

Test #12:

score: 0

Accepted

time: 3ms

memory: 7848kb

input:

output:

result:

ok 23 numbers

Test #13:

score: 0

Accepted

time: 3ms

memory: 7804kb

input:

output:

result:

ok 24 numbers

Test #14:

score: 0

Accepted

time: 3ms

memory: 7808kb

input:

output:

result:

ok 25 numbers

Test #15:

score: 0

Accepted

time: 4ms

memory: 7920kb

input:

output:

result:

ok 25 numbers

Test #16:

score: 0

Accepted

time: 22ms

memory: 8384kb

input:

output:

result:

ok 201 numbers

Test #17:

score: 0

Accepted

time: 27ms

memory: 6932kb

input:

output:

result:

ok 201 numbers

Test #18:

score: 0

Accepted

time: 3ms

memory: 8512kb

input:

output:

result:

ok 201 numbers

Test #19:

score: 0

Accepted

time: 3ms

memory: 6396kb

input:

output:

result:

ok 200 numbers

Test #20:

score: 0

Accepted

time: 1ms

memory: 8288kb

input:

output:

result:

ok 201 numbers

Test #21:

score: 0

Accepted

time: 3ms

memory: 6232kb

input:

output:

result:

ok 201 numbers

Test #22:

score: 0

Accepted

time: 3ms

memory: 8300kb

input:

output:

result:

ok 201 numbers

Test #23:

score: 0

Accepted

time: 2ms

memory: 10504kb

input:

output:

result:

ok 201 numbers

Test #24:

score: 0

Accepted

time: 1ms

memory: 10720kb

input:

output:

result:

ok 201 numbers

Test #25:

score: 0

Accepted

time: 1ms

memory: 15112kb

input:

output:

result:

ok 201 numbers

Test #26:

score: 0

Accepted

time: 7ms

memory: 23712kb

input:

output:

result:

ok 201 numbers

Test #27:

score: 0

Accepted

time: 27ms

memory: 33728kb

input:

output:

result:

ok 201 numbers

Test #28:

score: 0

Accepted

time: 25ms

memory: 21432kb

input:

output:

result:

ok 201 numbers

Test #29:

score: 0

Accepted

time: 60ms

memory: 12168kb

input:

output:

result:

ok 201 numbers

Test #30:

score: 0

Accepted

time: 41ms

memory: 8836kb

input:

output:

result:

ok 201 numbers

Test #31:

score: 0

Accepted

time: 7ms

memory: 8376kb

input:

output:

result:

ok 201 numbers

Test #32:

score: 0

Accepted

time: 37ms

memory: 8636kb

input:

output:

result:

ok 201 numbers

Test #33:

score: 0

Accepted

time: 7ms

memory: 10692kb

input:

output:

result:

ok 201 numbers

Test #34:

score: 0

Accepted

time: 19ms

memory: 9344kb

input:

output:

result:

ok 201 numbers

Test #35:

score: 0

Accepted

time: 3ms

memory: 8176kb

input:

output:

result:

ok 201 numbers

Test #36:

score: 0

Accepted

time: 2ms

memory: 8292kb

input:

output:

result:

ok 201 numbers

Test #37:

score: 0

Accepted

time: 2ms

memory: 8136kb

input:

output:

result:

ok 201 numbers

Test #38:

score: 0

Accepted

time: 3ms

memory: 6428kb

input:

output:

result:

ok 201 numbers

Test #39:

score: 0

Accepted

time: 1ms

memory: 8428kb

input:

output:

result:

ok 201 numbers

Test #40:

score: 0

Accepted

time: 4ms

memory: 8500kb

input:

output:

result:

ok 201 numbers

Test #41:

score: 0

Accepted

time: 1ms

memory: 8340kb

input:

output:

result:

ok 201 numbers

Test #42:

score: 0

Accepted

time: 1ms

memory: 8404kb

input:

output:

result:

ok 201 numbers

Test #43:

score: 0

Accepted

time: 3ms

memory: 8196kb

input:

output:

result:

ok 201 numbers

Test #44:

score: 0

Accepted

time: 4ms

memory: 8356kb

input:

output:

result:

ok 201 numbers

Test #45:

score: 0

Accepted

time: 3ms

memory: 6172kb

input:

output:

result:

ok 201 numbers

Test #46:

score: 0

Accepted

time: 204ms

memory: 8112kb

input:

output:

result:

ok 201 numbers

Test #47:

score: 0

Accepted

time: 508ms

memory: 11124kb

input:

output:

result:

ok 201 numbers

Test #48:

score: 0

Accepted

time: 323ms

memory: 8696kb

input:

output:

result:

ok 201 numbers

Test #49:

score: 0

Accepted

time: 208ms

memory: 8332kb

input:

output:

result:

ok 201 numbers

Test #50:

score: 0

Accepted

time: 694ms

memory: 10004kb

input:

output:

result:

ok 201 numbers

Test #51:

score: 0

Accepted

time: 128ms

memory: 8628kb

input:

output:

result:

ok 201 numbers

Test #52:

score: 0

Accepted

time: 176ms

memory: 8380kb

input:

output:

result:

ok 201 numbers

Test #53:

score: 0

Accepted

time: 332ms

memory: 9272kb

input:

output:

result:

ok 201 numbers

Test #54:

score: 0

Accepted

time: 14ms

memory: 7936kb

input:

output:

result:

ok 201 numbers

Test #55:

score: 0

Accepted

time: 161ms

memory: 8792kb

input:

output:

result:

ok 201 numbers

Test #56:

score: 0

Accepted

time: 93ms

memory: 8480kb

input:

output:

result:

ok 201 numbers

Test #57:

score: 0

Accepted

time: 29ms

memory: 7908kb

input:

output:

result:

ok 201 numbers

Test #58:

score: -100

Time Limit Exceeded

input: