QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#564888 | #4811. Be Careful | Harry27182 | WA | 2ms | 11776kb | C++14 | 3.0kb | 2024-09-15 16:35:48 | 2024-09-15 16:35:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
vector<int>e[205],e1[205],e2[205];
int f[100005],g[100005][205],tmp[100005][205],tmp2[100005][205],tmp3[100005];
int dp[205][205],n,suf[205][205],C[205][205],pw[205][205],u,v;
const int mod=998244353;
void Add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
void dfs(int u,int fa)
{
if(e[u].size()==1&&fa)return;
int num=0,B=0,mn=0x3f3f3f3f,mx=0;vector<int>vec;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v==fa)continue;
dfs(v,u);
if(e[v].size()==1)num++;
else vec.emplace_back(e[v].size()),mx=max(mx,(int)e[v].size());
}
sort(vec.begin(),vec.end());
for(int i=0;i<=vec.size();i++)
{
if((i==0?0:vec[i-1])+vec.size()-i+(i>10)<=mn)
{
mn=(i==0?0:vec[i-1])+vec.size()-i;
B=(i==0?0:vec[i-1]);
}
}
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v==fa)continue;
if(e[v].size()==1);
else if(e[v].size()<=B)e1[u].emplace_back(v);
else e2[u].emplace_back(v);
}
for(int i=0;i<(1<<B);i++)f[i]=0;
f[0]=1;
for(int i=0;i<e1[u].size();i++)
{
int v=e1[u][i];
for(int s=0;s<(1<<B);s++)tmp3[s]=f[s],f[s]=0;
for(int s=0;s<(1<<B);s++)
{
if(!tmp[s])continue;
for(int j=0;j<B;j++)Add(f[s|(1<<j)],1ll*tmp3[s]*dp[v][j]%mod);
}
}
for(int t=0;t<(1<<B);t++)
{
if(!f[t])continue;
for(int s=0;s<(1<<e2[u].size());s++)for(int j=0;j<=num;j++)g[s][j]=0;
g[0][0]=1;
for(int i=0;i<=e[u].size();i++)
{
for(int s=0;s<(1<<e2[u].size());s++)
{
for(int j=0;j<=num;j++)
{
if(!g[s][j])continue;
if(i<B&&((t>>i)&1))continue;
int now=1ll*f[t]*g[s][j]%mod;
for(int j=0;j<e2[u].size();j++)if(!((s>>j)&1))now=1ll*now*suf[e2[u][j]][i+1]%mod;
Add(dp[u][i],1ll*now*pw[n-i][num-j]%mod);
}
}
for(int s=0;s<(1<<e2[u].size());s++)for(int j=0;j<=num;j++)tmp[s][j]=g[s][j];
for(int s=0;s<(1<<e2[u].size());s++)
{
for(int k=0;k<=num;k++)
{
if(!g[s][k])continue;
for(int j=0;j<e2[u].size();j++)if(!((s>>j)&1))Add(g[s|(1<<j)][k],1ll*g[s][k]*dp[e2[u][j]][i]%mod);
}
}
for(int s=0;s<(1<<e2[u].size());s++)
{
for(int j=0;j<=num;j++)tmp2[s][j]=g[s][j],g[s][j]=0;
for(int j=0;j<=num;j++)
{
if(!tmp2[s][j])continue;
for(int k=j;k<=num;k++)Add(g[s][k],1ll*tmp2[s][j]*C[num-j][k-j]%mod);
}
}
if(i>=B||!((t>>i)&1))
{
for(int s=0;s<(1<<e2[u].size());s++)
{
for(int j=0;j<=num;j++)Add(g[s][j],mod-tmp[s][j]);
}
}
}
}
for(int i=n;i>=0;i--)
{
suf[u][i]=suf[u][i+1];
Add(suf[u][i],dp[u][i]);
}
}
int main()
{
//freopen("mex.in","r",stdin);
//freopen("mex.out","w",stdout);
cin.tie(0)->sync_with_stdio(0);
cin>>n;
for(int i=1;i<n;i++)cin>>u>>v,e[u].emplace_back(v),e[v].emplace_back(u);
for(int i=0;i<=n;i++)
{
pw[i][0]=1;
for(int j=1;j<=n;j++)pw[i][j]=1ll*pw[i][j-1]*i%mod;
}
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]=(C[i-1][j]+C[i-1][j-1])%mod;
}
dfs(1,0);
for(int i=0;i<=n;i++)cout<<dp[1][i]<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9820kb
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: 0ms
memory: 7672kb
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: 11776kb
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: 1ms
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: 9992kb
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: 7676kb
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: 0ms
memory: 9848kb
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: -100
Wrong Answer
time: 0ms
memory: 7772kb
input:
10 3 6 2 4 4 9 8 4 2 5 10 5 3 7 2 1 1 3
output:
48510 33242 202399 0 0 0 0 0 0 0 0
result:
wrong answer 1st numbers differ - expected: '27510', found: '48510'