QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#78579#4811. Be CarefulhuzhaoyangWA 3ms44704kbC++143.4kb2023-02-19 16:20:142023-02-19 16:20:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-19 16:20:16]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:44704kb
  • [2023-02-19 16:20:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=205,M=19,mod=998244353;
int n,K,x,y,d[N],l[N],t[N],pw[N],C[N][N];
int fs[N],f[N][N],h[1<<M],sum[N][1<<M],g[N][1<<M],g0[N][1<<M];
vector<int>v,e[N];
int lowbit(int k){
	return (k&(-k));
}
int add(int x,int y){
	x+=y;
	return (x<mod ? x : x-mod);
}
void dfs(int k,int fa){
	for(int son:e[k])
		if (son!=fa){
			dfs(son,k),d[k]++;
			if (!d[son])l[k]++;
		}
	if (!d[k]){
		for(int i=0;i<=n;i++)f[k][i]=1;
		return;
	}
	int K=0;
//	int K=0,mn=d[k]-l[k];
//	for(int i=1;i<=d[k];i++){
//		int s=i;
//		for(int son:e[k])
//			if ((son!=fa)&&(d[son]>i))s++;
//		if (mn>s)K=i,mn=s;
//	}
	v.clear();
	for(int son:e[k])
		if ((son!=fa)&&(d[son]>K))v.push_back(son);
	t[k]=v.size();
	for(int son:e[k])
		if (son!=fa){
			for(int i=0;i<=K;i++)sum[son][1<<i]=f[son][i];
			for(int T=1;T<(1<<K+1);T++){
				int T0=(T&(-T));
				sum[son][T]=add(sum[son][T0],sum[son][T^T0]);
			}
		}
	for(int son:e[k])
		if (son!=fa){
			for(int i=K+1;i<=n;i++)fs[son]=add(fs[son],f[son][i]);
		}
	for(int i=K;i>=0;i--){
		for(int T=0;T<(1<<i);T++){
			int s=(i-__builtin_popcount(T)&1 ? mod-1 : 1);
			for(int son:e[k])
				if (son!=fa)s=(ll)s*(fs[son]+sum[son][T])%mod;
			f[k][i]=add(f[k][i],s); 
		}
		for(int son:e[k])
			if (son!=fa)fs[son]=add(fs[son],f[son][i]);
	}
	if (K==d[k])return;
	for(int i=0;i<=l[k];i++)
		for(int S=0;S<(1<<t[k]);S++)g[i][S]=0;
	for(int T=0;T<(1<<K+1);T++){
		int s=(K+1-__builtin_popcount(T)&1 ? mod-1 : 1);
		for(int son:e[k])
			if ((d[son])&&(d[son]<=K))s=(ll)s*sum[son][T]%mod;
		h[0]=1;
		for(int i=0;i<t[k];i++)h[1<<i]=sum[v[i]][T];
		for(int S=0;S<(1<<t[k]);S++){
			int S0=lowbit(S);
			h[S]=(ll)h[S0]*h[S^S0]%mod;
		}
		pw[0]=1,pw[1]=__builtin_popcount(T);
		for(int i=2;i<=l[k];i++)pw[i]=(ll)pw[i-1]*pw[1]%mod;
		for(int S=0;S<(1<<t[k]);S++){
			int s0=(ll)s*h[(1<<t[k])-1^S]%mod;
			for(int x=0;x<=l[k];x++)
				g[x][S]=(g[x][S]+(ll)s0*C[l[k]][x]%mod*pw[l[k]-x])%mod;
		}
	}
	for(int son:v){
		fs[son]=0;
		for(int i=K+1;i<=d[k];i++)fs[son]=add(fs[son],f[son][i]);
	}
	for(int i=K+1;i<=d[k];i++){
		pw[0]=1,pw[1]=n-i;
		for(int i=2;i<=l[k];i++)pw[i]=(ll)pw[i-1]*pw[1]%mod;
		for(int son:v)fs[son]=add(fs[son],mod-f[son][i]);
		for(int x=0;x<=l[k];x++){
			h[0]=1;
			for(int i=0;i<t[k];i++)h[1<<i]=fs[v[i]];
			for(int S=0;S<(1<<t[k]);S++){
				int S0=lowbit(S);
				h[S]=(ll)h[S0]*h[S^S0]%mod;
			}
			for(int S=0;S<(1<<t[k]);S++)
				f[k][i]=(f[k][i]+(ll)pw[x]*g[x][S]%mod*h[S])%mod;
		}
		if (i==d[k])continue;
		for(int x=0;x<=l[k];x++)
			for(int S=0;S<(1<<t[k]);S++)g0[x][S]=g[x][S];
		for(int x=0;x<=l[k];x++)
			for(int y=0;y<x;y++)
				for(int S=0;S<(1<<t[k]);S++)
					g[y][S]=(g[y][S]+(ll)g[x][S]*C[x][y])%mod;
		for(int j=0;j<t[k];j++)
			for(int x=0;x<=l[k];x++)
				for(int S=0;S<(1<<t[k]);S++)
					if ((S>>j)&1){
						int S0=(S^(1<<j));
						g[x][S0]=(g[x][S0]+(ll)g[x][S]*f[v[j]][i])%mod;
					}
		for(int x=0;x<=l[k];x++)
			for(int S=0;S<(1<<t[k]);S++)g[x][S]=add(g[x][S],mod-g0[x][S]);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x); 
	}
	for(int i=0;i<=n;i++){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++)C[i][j]=add(C[i-1][j],C[i-1][j-1]);
	}
	dfs(1,0);
	for(int i=0;i<=n;i++)printf("%d\n",f[1][i]);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 15924kb

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

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: 3ms
memory: 9864kb

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: 9816kb

input:

2
1 2

output:

2
1
0

result:

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

Test #5:

score: 0
Accepted
time: 1ms
memory: 44704kb

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

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

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

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

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
463557323
253920328
0
0
0
0
0
0
0
0
0
0
0
0

result:

wrong answer 2nd numbers differ - expected: '780146137', found: '463557323'