QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#75514 | #4811. Be Careful | sincop70 | WA | 3ms | 7764kb | C++14 | 3.4kb | 2023-02-05 15:27:39 | 2023-02-05 15:27:40 |
Judging History
answer
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int maxn=205,maxm=(1<<19),mod=998244353;
int n;
int ksm(int b,int p){int ret=1;while(p){if(p&1)ret=1ll*ret*b%mod;p>>=1;b=1ll*b*b%mod;}return ret;}
vector<int> G[maxn];
int f[maxn][maxn],sdp[maxn][maxn],g[maxm],h[maxm][maxn],w[maxm];
int deg[maxn],ss[maxn],pw[maxn][maxn];
inline int add(const int x,const int y){return (x+y>mod)>=mod?x+y-mod:x+y;}
void dfs(int u,int fa)
{
if(G[u].size()==1&&fa){for(int i=0;i<=n;i++)f[u][i]=1,sdp[u][i]=n-i+1;return;}
int lfc=0;
for(int v:G[u])if(v!=fa){dfs(v,u);deg[u]++;if(!deg[v])lfc++;}
memset(ss,0,sizeof ss);
for(int v:G[u])if(v!=fa)ss[deg[v]]++;
for(int i=1;i<=n;i++)ss[i]+=ss[i-1];
int B=0,mn=1e9;
for(int i=0;i<=n;i++)
if(i<=18&&ss[n]-ss[i]<=18&&i+ss[n]-ss[i]<mn)
mn=i+ss[n]-ss[i],B=i;
vector<int> S1,S2;
for(int v:G[u])if(v!=fa&°[v])
{
if(deg[v]>B)S2.push_back(v);
else S1.push_back(v);
}
int len=S2.size();
const int M1=(1<<B+1);
const int M2=(1<<len);
for(int s=0;s<M1;s++)
{
g[s]=1;
for(int v:S1)
{
int sum=0;
for(int i=0;i<=B;i++)
if(!(s&(1<<i)))sum=add(sum,f[v][i]);
g[s]=1ll*g[s]*sum%mod;
}
}
for(int i=0;i<=B;i++)
for(int s=0;s<M1;s++)
if(!(s&(1<<i)))
g[s]=add(g[s],mod-g[s^(1<<i)]);
//容斥,当前的g表示s不选,其他选的方案
for(int cs=0;cs<M1;cs++)
if(g[cs])
{
for(int s=0;s<M2;s++)
for(int i=0;i<=deg[u];i++)
h[s][i]=0;
h[0][0]=g[cs];
for(int i=0;i<=deg[u];i++)
{
if(i>B||(cs&(1<<i)))
{
w[0]=1;
for(int s=1;s<M2;s++)
{
int b=__builtin_ctz(s);
w[s]=1ll*w[s^(1<<b)]*sdp[S2[b]][i+1]%mod;//w[s]为钦定不能选在前面的值
}
for(int s=0;s<M2;s++)
for(int j=0;j<=deg[u];j++)
if(h[s][j])
f[u][i]=add(f[u][i],1ll*(j&1?mod-1:1)*h[s][j]%mod*w[(M2-1)^s]%mod*pw[n-j][lfc]%mod);//容斥,i之前定下有j个位置不选,枚举在前面放了哪些点,叶子随便
}
for(int j=i;j>=0;j--)
{
if(i>B||(cs&(1<<i)))for(int s=0;s<M2;s++)h[s][j+1]=add(h[s][j],h[s][j+1]);
for(int k=0;k<len;k++)
for(int s=0;s<M2;s++)
if(!(s&(1<<k)))h[s|(1<<k)][j]=add(h[s|(1<<k)][j],1ll*h[s][j]*f[S2[k]][i]%mod);
}
}
}
for(int i=n;i>=0;i--)sdp[u][i]=add(sdp[u][i+1],f[u][i]);
while(!sdp[deg[u]])deg[u]--;
}
signed main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
pw[i][0]=1;
for(int j=1;j<=n;j++)
pw[i][j]=1ll*pw[i][j-1]*i%mod;
}
dfs(1,0);
for(int i=0;i<=n;i++)
printf("%d\n",f[1][i]);
return 0;
}
/*
5
1 2
1 3
2 4
2 5
8
1 2
1 3
1 4
1 5
1 6
6 7
6 8
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 7764kb
input:
5 1 2 1 3 2 4 2 5
output:
55 998244480 998244387 0 0 0
result:
wrong answer 2nd numbers differ - expected: '127', found: '998244480'