QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#75494 | #4811. Be Careful | sincop70 | WA | 7ms | 9816kb | C++14 | 3.1kb | 2023-02-05 14:14:18 | 2023-02-05 14:14:21 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
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[maxn];
int deg[maxn],ss[maxn];
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;memset(ss,0,sizeof ss);
for(int v:G[u])if(v!=fa){dfs(v,u);deg[u]++;if(!deg[v])lfc++;ss[deg[v]]++;}
for(int i=1;i<=n;i++)ss[i]+=ss[i-1];
int B=0,mn=1e18;
for(int i=0;i<=n;i++)
if(i<=18&&ss[n]-ss[i]<=18&&(1ll<<i)*i+(1ll<<i+ss[n]-ss[i])*deg[u]<mn)
mn=(1ll<<i)*i+(1ll<<i+ss[n]-ss[i])*deg[u],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();
for(int s=0;s<(1<<B+1);s++)
{
g[s]=1;
for(int v:S1)
{
int sum=0;
for(int i=0;i<=B;i++)
if(!(s&(1<<i)))sum=(sum+f[v][i])%mod;
g[s]=1ll*g[s]*sum%mod;
}
}
for(int i=0;i<=B;i++)
for(int s=0;s<(1<<B+1);s++)
if(!(s&(1<<i)))
g[s]=(g[s]-g[s^(1<<i)]+mod)%mod;
//容斥,当前的g表示s不选,其他选的方案
for(int cs=0;cs<(1<<B+1);cs++)
if(g[cs])
{
for(int s=0;s<(1<<len);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<(1<<len);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<(1<<len);s++)
for(int j=0;j<=deg[u];j++)
f[u][i]=(f[u][i]+(1ll*(j&1?-1:1)*h[s][j]*w[((1<<len)-1)^s]%mod*ksm(n-j,lfc)%mod)%mod+mod)%mod;//容斥,i之前定下有j个位置不选,枚举在前面放了哪些点,叶子随便放
}
for(int j=i;j>=0;j--)
{
if(i>B||(cs&(1<<i)))for(int s=0;s<(1<<len);s++)h[s][j+1]=(h[s][j]+h[s][j+1])%mod;
for(int s=0;s<(1<<len);s++)
for(int k=0;k<len;k++)
if(!(s&(1<<k)))h[s|(1<<k)][j]=(h[s|(1<<k)][j]+1ll*h[s][j]*f[S2[k]][i]%mod)%mod;
}
}
}
//for(int i=0;i<=n;i++)printf("%lld ",f[u][i]);
//putchar('\n');
for(int i=n;i>=0;i--)sdp[u][i]=(sdp[u][i+1]+f[u][i])%mod;
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%lld%lld",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
for(int i=0;i<=n;i++)
printf("%lld\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
*/
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 5740kb
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: 7868kb
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: 5740kb
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: 2ms
memory: 5832kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 2ms
memory: 5760kb
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: 2ms
memory: 5732kb
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: 2ms
memory: 7824kb
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: 2ms
memory: 5760kb
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: 0
Accepted
time: 7ms
memory: 9816kb
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 780146137 253920328 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 15 numbers
Test #10:
score: -100
Wrong Answer
time: 1ms
memory: 5784kb
input:
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
output:
572808214 968306869 162981267 410610406 465749894 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
wrong answer 2nd numbers differ - expected: '694156482', found: '968306869'