QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#407353#4811. Be Carefulcrazy_seaWA 1ms7900kbC++143.1kb2024-05-08 16:21:482024-05-08 16:21:49

Judging History

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

  • [2024-05-08 16:21:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7900kb
  • [2024-05-08 16:21:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N=210,mod=998244353,M=(1<<20);
struct edge{
	int next,to;
}e[N<<1];
int first[N],len,n,leaf[N],mx[N],fa[N];
void add(int a,int b)
{
	e[++len]=edge{first[a],b};
	first[a]=len;
}
bool chk(int x,int a)
{
	if(a<=30) return x>>a&1;
	return 0;
}
ll fastpow(ll a,int b)
{
	ll s=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1) s=s*a%mod;
	return s;
}
vector<ll> v1[N],v2[N];
ll fac[N],ifac[N],S[N][N],H[N][N],dp[N][N],s[N];
void pls(ll &a,ll b){a=(a+b)%mod;}
ll C(int a,int b){return a<b||b<0?0:fac[a]*ifac[b]%mod*ifac[a-b]%mod;}
void work(int x,ll a,int p,int cnt,vi v)
{
	int m=v.size();
	reverse(v.begin(),v.end());
	for(int i=0;i<=cnt;i++)
		v1[i].resize(1<<m),v2[i].resize(1<<m);
	v1[0][(1<<m)-1]=1;
	for(int i=0;i<m;i++)
	{
		s[i]=0;
		for(int j=0;j<=mx[v[i]];j++)
			pls(s[i],dp[v[i]][j]);
	}
	for(int i=0;i<=mx[x];i++)
	{
		for(int j=0;j<m;j++) pls(s[j],mod-dp[v[j]][i]);
		if(!chk(p,i))
			for(int j=0;j<=cnt;j++)
				for(int k=0;k<(1<<m);k++)
				{
					ll res=v2[j][k]=v1[j][k];
					res=res*H[j][n-i]%mod;
					if(!res) break;
					for(int x=0;x<m;x++)
						if(k>>x&1) res=res*s[x]%mod;
					pls(dp[x][i],res*a);
				}
		for(int x=0;x<m;x++)
			for(int j=0;j<=cnt;j++)
				for(int k=0;k<(1<<m);k++)
					if(k>>x&1) pls(v1[j][k^(1<<x)],v1[j][k]*dp[v[x]][i]);
		for(int j=cnt-1;j>=0;j--)
			for(int k=0;k<(1<<m);k++)
				pls(v1[j+1][k],v1[j][k]);
		if(!chk(p,i))
			for(int j=0;j<=cnt;j++)
				for(int k=0;k<(1<<m);k++)
					pls(v1[j][k],mod-v2[j][k]);
		while(m&&mx[v[m-1]]==i) m--;
	}
	for(int i=0;i<=cnt;i++) v1[i].clear();
}
ll f[M],g[M];
void trans(int p,int x)
{
	for(int i=0;i<(1<<p);i++)
		for(int j=0;j<=mx[x];j++)
			pls(g[i|(1<<j)],f[i]*dp[x][j]);
	for(int i=0;i<(1<<(mx[x]+1));i++)
		f[i]=g[i],g[i]=0;
}
void dfs(int x)
{
	leaf[x]=1;
	vi v;
	int cnt=0;
	for(int i=first[x],y;i;i=e[i].next)
		if((y=e[i].to)!=fa[x])
		{
			fa[y]=x,dfs(y),leaf[x]=0;
			if(leaf[y]) cnt++;
			else v.push_back(y);
		}
	mx[x]=cnt+(int)v.size();
	if(leaf[x]) return;
	sort(v.begin(),v.end(),[](int x,int y){return mx[x]<mx[y];});
	int val=1,w=-1;
	for(int i=0;i<(int)v.size();i++)
		if(mx[v[i]]-i<=val) val=mx[v[i]]-i,w=i;
	f[0]=1;
	int P=0;
	for(int i=0;i<=w;i++) trans(P,v[i]),P=mx[v[i]]+1;
	for(int i=0;i<=cnt;i++)
		for(int j=0;j<=n;j++)
		{
			H[i][j]=0;
			for(int k=i;k<=cnt;k++)
				pls(H[i][j],S[k][i]*fac[i]%mod*C(cnt,k)%mod*fastpow(j,cnt-k));
		}
	for(int i=0;i<(1<<P);i++)
		if(f[i]) work(x,f[i],i,cnt,vi(v.begin()+w+1,v.end()));
	for(int i=0;i<(1<<P);i++) f[i]=g[i]=0;
}
void init(int n)
{
	fac[0]=ifac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	ifac[n]=fastpow(fac[n],mod-2);
	for(int i=n-1;i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
	S[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			S[i][j]=(S[i-1][j-1]+S[i-1][j]*j)%mod;
}
int main()
{
	scanf("%d",&n);
	if(n==1) return puts("1"),0;
	init(n);
	for(int i=1,x,y;i<n;i++)
		scanf("%d%d",&x,&y),add(x,y),add(y,x);
	dfs(1);
	for(int i=0;i<=n;i++) printf("%lld\n",dp[1][i]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 7900kb

input:

5
1 2
1 3
2 4
2 5

output:

0
135
70
0
0
0

result:

wrong answer 1st numbers differ - expected: '55', found: '0'