QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#85056#4811. Be Careful_UMqwq_WA 2ms4316kbC++143.7kb2023-03-06 22:18:232023-03-06 22:18:27

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 22:18:27]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4316kb
  • [2023-03-06 22:18:23]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define MAXN 210
#define p 998244353
#define pb push_back
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int N=200;
int add(int x,int y){return x+y<p?x+y:x+y-p;}
int del(int x,int y){return x-y<0?x-y+p:x-y;}
int n,in[MAXN];
int pw[MAXN][MAXN],C[MAXN][MAXN];
struct Node{int to,nxt;}Edge[MAXN<<1];
int Head[MAXN],cnt_Edge;
void Add_Edge(int u,int v){
	Edge[++cnt_Edge]=(Node){v,Head[u]};
	Head[u]=cnt_Edge;
}
int f[MAXN][MAXN],suf[MAXN],deg[MAXN];
vector<int>cnt[MAXN];
void dp(int u,int fa){
	if(in[u]==1&&u>1){
		for(int i=0;i<=n;i++)f[u][i]=1;
		return;
	}
	vector<int>son;int lef=0;
	for(int i=Head[u];i;i=Edge[i].nxt){
		int v=Edge[i].to;if(v==fa)continue;
		dp(v,u);deg[u]++;son.pb(v);
		if(!deg[v])lef++;
	}//cerr<<u<<' '<<deg[u]<<endl;
	int mn=inf,B=0,sz=0;
	for(int i=1;i<20;i++){
		int cnt=0;
		for(auto v:son)cnt+=(deg[v]>=i);
		if(i+cnt<mn)mn=i+cnt,B=i,sz=cnt;
	}//cerr<<u<<' '<<B<<' '<<sz<<' '<<lef<<endl;
	for(auto v:son){
		cnt[v].resize(1<<B);
		for(int s=1;s<(1<<B);s++){
			int i=__builtin_ctz(s);
			cnt[v][s]=add(cnt[v][s^(1<<i)],f[v][i]);
		}
		for(int i=B;i<=n;i++)suf[v]=add(suf[v],f[v][i]);
	}
	//part 1: i<B
	for(int i=B-1;i>=0;i--){
		for(int s=0;s<(1<<i);s++){
			int sum=((i-__builtin_popcount(s))&1?p-1:1);
			for(auto v:son)sum=sum*(suf[v]+cnt[v][s])%p;
			f[u][i]=add(f[u][i],sum);
		}
		for(auto v:son)suf[v]=add(suf[v],f[v][i]);
	}
	//part 2: i>=B
	vector<int>nxt,pre;
	for(auto v:son){
		suf[v]=0;
		for(int i=B;i<=n;i++)suf[v]=add(suf[v],f[v][i]);
		if(deg[v]>=B)nxt.pb(v);
		else if(deg[v])pre.pb(v);//,cerr<<"pre:"<<v<<endl;
	}
	vector<vector<int>>g;g.resize(lef+1);
	for(int i=0;i<=lef;i++)g[i].resize(1<<sz);
	vector<int>ts;ts.resize(1<<sz);ts[0]=1;
	for(int s=0;s<(1<<B);s++){
		int co=((B-__builtin_popcount(s))&1?p-1:1);
		for(auto v:pre)co=co*cnt[v][s]%p;
		for(int t=1;t<(1<<sz);t++){
			int i=__builtin_ctz(t);
			ts[t]=ts[t^(1<<i)]*cnt[nxt[i]][s]%p;
		}
		int pcnt=__builtin_popcount(s);
		for(int i=0;i<=lef;i++)
			for(int t=0;t<(1<<sz);t++)
				g[i][t]=(g[i][t]+co*pw[pcnt][i]%p*ts[t])%p;//,cerr<<"init:"<<s<<' '<<i<<' '<<t<<' '<<co<<' '<<C[lef][i]<<' '<<pw[pcnt][i]<<' '<<ts[t]<<endl;
	}
	int U=(1<<sz)-1;
	for(int i=B;i<=deg[u];i++){
		for(auto v:nxt)suf[v]=del(suf[v],f[v][i]);
		for(int s=1;s<(1<<sz);s++){
			int j=__builtin_ctz(s);//cerr<<s<<' '<<j<<' '<<nxt[j]<<' '<<suf[nxt[j]]<<endl;
			ts[s]=ts[s^(1<<j)]*suf[nxt[j]]%p;
		}
		for(int j=0;j<=lef;j++)
			for(int s=0;s<(1<<sz);s++)
				f[u][i]=(f[u][i]+g[j][s]*pw[n-i][lef-j]%p*ts[U^s]%p*C[lef][j])%p;//,cerr<<"calc:"<<i<<' '<<j<<' '<<s<<' '<<g[j][s]<<' '<<pw[n-i][lef-j]<<' '<<ts[U^s]<<' '<<C[lef][j]<<endl;
		auto tmp=g;
		for(int s=0;s<(1<<sz);s++)
			for(int j=lef;j>=0;j--)
				for(int k=lef;k>j;k--)
					g[k][s]=(g[k][s]+g[j][s]*C[k][j])%p;//,cerr<<"trans:"<<k<<' '<<j<<' '<<s<<' '<<C[k][j]<<endl;
		for(int j=0;j<=lef;j++)
			for(int s=0;s<(1<<sz);s++)
				for(int k=0;k<sz;k++){
					if((s>>k)&1)continue;
					int t=s|(1<<k);
					g[j][t]=(g[j][t]+g[j][s]*f[nxt[k]][i])%p;
				}
		for(int j=0;j<=lef;j++)
			for(int s=0;s<(1<<sz);s++)g[j][s]=del(g[j][s],tmp[j][s]);//,cerr<<"del:"<<j<<' '<<s<<' '<<tmp[j][s]<<endl;
	}
//	cerr<<"f:"<<u<<endl;
//	for(int i=0;i<=n;i++)cerr<<f[u][i]<<' ';cerr<<endl;
}
signed main(){
	for(int i=0;i<=N;i++){
		pw[i][0]=1;
		for(int j=1;j<=N;j++)pw[i][j]=pw[i][j-1]*i%p;
	}
	C[0][0]=1;
	for(int i=1;i<=N;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)C[i][j]=add(C[i-1][j],C[i-1][j-1]);
	}
	scanf("%lld",&n);
	for(int i=1;i<n;i++){
		int u,v;scanf("%lld%lld",&u,&v);
		Add_Edge(u,v);Add_Edge(v,u);
		in[u]++;in[v]++;
	}
	dp(1,0);
	for(int i=0;i<=n;i++)printf("%lld\n",f[1][i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4288kb

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: 2ms
memory: 4316kb

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: 2ms
memory: 4248kb

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: 2ms
memory: 4304kb

input:

2
1 2

output:

2
1
0

result:

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

Test #5:

score: 0
Accepted
time: 2ms
memory: 4272kb

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: 2ms
memory: 4272kb

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: 2ms
memory: 4312kb

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: 2ms
memory: 4312kb

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: 1ms
memory: 4292kb

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: -100
Wrong Answer
time: 0ms
memory: 4308kb

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:

304111417
708452002
811887559
304801540
293771122
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

wrong answer 1st numbers differ - expected: '572808214', found: '304111417'