QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75494#4811. Be Carefulsincop70WA 7ms9816kbC++143.1kb2023-02-05 14:14:182023-02-05 14:14:21

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 14:14:21]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:9816kb
  • [2023-02-05 14:14:18]
  • 提交

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&&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;
    //容斥,当前的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
*/

Details

Tip: Click on the bar to expand more detailed information

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'