QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75514#4811. Be Carefulsincop70WA 3ms7764kbC++143.4kb2023-02-05 15:27:392023-02-05 15:27:40

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 15:27:40]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:7764kb
  • [2023-02-05 15:27:39]
  • 提交

answer

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
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],pw[maxn][maxn];
inline int add(const int x,const int y){return (x+y>mod)>=mod?x+y-mod:x+y;}
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=1e9;
    for(int i=0;i<=n;i++)
        if(i<=18&&ss[n]-ss[i]<=18&&i+ss[n]-ss[i]<mn)
            mn=i+ss[n]-ss[i],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();
    const int M1=(1<<B+1);
    const int M2=(1<<len);
	for(int s=0;s<M1;s++)
	{
		g[s]=1;
		for(int v:S1)
        {
            int sum=0;
            for(int i=0;i<=B;i++)
                if(!(s&(1<<i)))sum=add(sum,f[v][i]);
            g[s]=1ll*g[s]*sum%mod;
        }
	}
    for(int i=0;i<=B;i++)
        for(int s=0;s<M1;s++)
            if(!(s&(1<<i)))
                g[s]=add(g[s],mod-g[s^(1<<i)]);
    //容斥,当前的g表示s不选,其他选的方案
    for(int cs=0;cs<M1;cs++)
    if(g[cs])
    {
        for(int s=0;s<M2;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<M2;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<M2;s++)
                    for(int j=0;j<=deg[u];j++)
                        if(h[s][j])
                            f[u][i]=add(f[u][i],1ll*(j&1?mod-1:1)*h[s][j]%mod*w[(M2-1)^s]%mod*pw[n-j][lfc]%mod);//容斥,i之前定下有j个位置不选,枚举在前面放了哪些点,叶子随便
            }
            for(int j=i;j>=0;j--)
            {
                if(i>B||(cs&(1<<i)))for(int s=0;s<M2;s++)h[s][j+1]=add(h[s][j],h[s][j+1]);
                for(int k=0;k<len;k++)
                     for(int s=0;s<M2;s++)
                         if(!(s&(1<<k)))h[s|(1<<k)][j]=add(h[s|(1<<k)][j],1ll*h[s][j]*f[S2[k]][i]%mod);
            }
        }
    }
    for(int i=n;i>=0;i--)sdp[u][i]=add(sdp[u][i+1],f[u][i]);
    while(!sdp[deg[u]])deg[u]--;
}
signed main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
    for(int i=1;i<=n;i++)
    {
        pw[i][0]=1;
        for(int j=1;j<=n;j++)
            pw[i][j]=1ll*pw[i][j-1]*i%mod;
    }
    dfs(1,0);
    for(int i=0;i<=n;i++)
        printf("%d\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: 0
Wrong Answer
time: 3ms
memory: 7764kb

input:

5
1 2
1 3
2 4
2 5

output:

55
998244480
998244387
0
0
0

result:

wrong answer 2nd numbers differ - expected: '127', found: '998244480'