QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#407353 | #4811. Be Careful | crazy_sea | WA | 1ms | 7900kb | C++14 | 3.1kb | 2024-05-08 16:21:48 | 2024-05-08 16:21:49 |
Judging History
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'