QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#75509 | #4811. Be Careful | sincop70 | TL | 865ms | 11948kb | C++14 | 3.5kb | 2023-02-05 15:12:24 | 2023-02-05 15:12:27 |
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[maxm];
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;
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=1e18;
for(int i=0;i<=n;i++)
{
int j=ss[n]-ss[i];
if(i<=18&&j<=18&&i*(deg[u]-lfc-j)*(1ll<<i)+deg[u]*(deg[u]+j)*(1ll<<(i+ss[n]-ss[i])))
mn=i*(deg[u]-lfc-j)*(1ll<<i)+deg[u]*(deg[u]+j)*(1ll<<(i+ss[n]-ss[i])),B=i;
}
vector<int> S1,S2;
//printf("!%lld %lld %lld\n",u,B,lfc);
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;
//for(int i=0;i<(1<<B+1);i++)
// printf("%lld ",g[i]);putchar('\n');
//容斥,当前的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++)
if(h[s][j])
{
f[u][i]=(f[u][i]+1ll*(j&1?mod-1:1)*h[s][j]%mod*w[((1<<len)-1)^s]%mod*ksm(n-j,lfc)%mod)%mod;//容斥,i之前定下有j个位置不选,枚举在前面放了哪些点,叶子随便放
//printf("%d %d %d %d %d\n",u,i,f[u][i],h[s][j],w[((1<<len)-1)^s]);
}
}
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 k=0;k<len;k++)
for(int s=0;s<(1<<len);s++)
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
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: 100
Accepted
time: 3ms
memory: 9824kb
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: 3ms
memory: 9928kb
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: 3ms
memory: 7772kb
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: 3ms
memory: 7740kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 2ms
memory: 7764kb
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: 3ms
memory: 9908kb
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: 1ms
memory: 7760kb
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: 1ms
memory: 9812kb
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: 8ms
memory: 7836kb
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: 0
Accepted
time: 320ms
memory: 10184kb
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 694156482 763085092 958730326 465749894 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 21 numbers
Test #11:
score: 0
Accepted
time: 390ms
memory: 11948kb
input:
21 6 12 11 13 1 7 8 14 1 18 5 4 1 2 16 11 21 1 9 10 15 17 1 9 1 8 1 20 1 3 1 4 19 16 11 1 15 10 3 6
output:
778184256 242901486 277265229 855621813 564317020 918444623 408876720 314039448 593931360 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 22 numbers
Test #12:
score: 0
Accepted
time: 641ms
memory: 11132kb
input:
22 20 21 9 12 6 10 19 10 16 10 10 11 8 7 13 12 21 22 19 20 14 13 7 6 8 9 15 14 2 5 18 6 5 6 3 2 16 17 2 1 3 4
output:
142157709 5878180 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 23 numbers
Test #13:
score: 0
Accepted
time: 686ms
memory: 10812kb
input:
23 6 10 4 2 6 9 15 20 10 15 3 6 17 23 1 3 16 22 19 14 17 12 7 11 18 13 11 16 5 3 8 5 10 14 8 12 9 13 4 7 1 2 15 21
output:
7619809 175546557 7936610 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 24 numbers
Test #14:
score: 0
Accepted
time: 865ms
memory: 11860kb
input:
24 7 10 2 5 2 1 17 20 1 4 16 13 7 4 19 16 23 20 11 8 10 13 1 3 22 19 5 8 3 6 17 14 21 18 24 21 18 15 9 6 9 12 14 11 15 12
output:
24 576 15025 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 25 numbers
Test #15:
score: 0
Accepted
time: 713ms
memory: 11136kb
input:
24 22 16 17 11 15 9 13 7 8 2 1 3 5 1 6 12 9 3 14 8 21 15 17 23 19 13 7 1 24 18 2 1 5 11 1 4 4 10 18 12 20 14 10 16 1 6
output:
24 7962624 236177977 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 25 numbers
Test #16:
score: 0
Accepted
time: 13ms
memory: 10968kb
input:
200 1 199 95 1 1 75 177 1 66 1 157 1 85 1 1 193 1 26 8 1 38 1 151 1 1 56 63 1 1 138 1 59 190 1 1 36 1 120 156 1 115 1 1 118 171 1 6 1 113 1 20 1 83 1 1 176 33 1 153 1 1 169 22 1 1 159 1 27 87 1 1 129 1 44 174 1 1 93 77 1 1 122 1 125 1 23 1 81 112 1 173 1 1 51 32 1 96 1 184 1 116 1 67 1 1 94 1 104 19...
output:
211917199 369375874 201944418 582671162 183066248 639389350 952947539 137147613 216366713 398936459 73236543 354059031 727857197 121548413 610762100 573534011 706945631 286154195 226699593 267771858 823273748 233587424 176942776 226493975 707601105 339075191 694353149 944734662 932707579 934386415 4...
result:
ok 201 numbers
Test #17:
score: 0
Accepted
time: 29ms
memory: 10512kb
input:
200 2 199 95 2 2 75 177 2 66 2 157 2 85 2 2 193 2 26 8 2 38 2 151 2 2 56 63 2 2 138 2 59 190 2 2 36 2 120 156 2 115 2 2 118 171 2 6 2 113 2 20 2 83 2 2 176 33 2 153 2 2 169 22 2 2 159 2 27 87 2 2 129 2 44 174 2 2 93 77 2 2 122 2 125 2 23 2 81 112 2 173 2 2 51 32 2 96 2 184 2 116 2 67 2 2 94 2 104 19...
output:
356210711 85910356 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 201 numbers
Test #18:
score: -100
Time Limit Exceeded
input:
200 198 199 95 94 74 75 177 176 66 65 157 156 85 84 192 193 25 26 8 7 38 37 151 150 55 56 63 62 137 138 58 59 190 189 35 36 119 120 156 155 115 114 117 118 171 170 6 5 113 112 20 19 83 82 175 176 33 32 153 152 168 169 22 21 158 159 26 27 87 86 128 129 43 44 174 173 92 93 77 76 121 122 124 125 22 23 ...