QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75509#4811. Be Carefulsincop70TL 865ms11948kbC++143.5kb2023-02-05 15:12:242023-02-05 15:12:27

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 15:12:27]
  • Judged
  • Verdict: TL
  • Time: 865ms
  • Memory: 11948kb
  • [2023-02-05 15:12:24]
  • Submitted

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&&deg[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
...

output:


result: