QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412276#8669. 正方形计数lg100 1ms3936kbC++141.3kb2024-05-16 11:28:482024-05-16 11:28:49

Judging History

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

  • [2024-05-16 11:28:49]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3936kb
  • [2024-05-16 11:28:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

constexpr int N=22,M=N*N;
constexpr int mod=998244353;

int k;
int sz[N];
int f[N][M][N],t[M][N];
int he[N],ne[N<<1],to[N<<1];

void add(int a,int b,int idx)
{
    to[idx]=b,ne[idx]=he[a],he[a]=idx;
}

void Add(int &a,int b)
{
    (a+=b),(a>=mod?a-=mod:0);
}

void dfs(int u,int fa)
{
    sz[u]=1;
    for(int i=1;i<=k;i++)f[u][0][i]=1;
    for(int i=he[u];i;i=ne[i])
    {
        int v=to[i];
        if(v==fa)continue;
        dfs(v,u);
        memset(t,0,sizeof t);
        for(int i=0;i<=k*sz[u];i++)
            for(int j=0;j<=k;j++)
            {
                if(!f[u][i][j])continue;
                for(int p=0;p<=k*sz[v];p++)
                    for(int q=0;q<=k;q++)
                        if(f[v][p][q])Add(t[i+p+q][max(i+j+p,i+p+q)-(i+p+q)],1ll*f[u][i][j]*f[v][p][q]%mod);
            }
        memcpy(f[u],t,sizeof t);
        sz[u]+=sz[v];
    }
}

int main()
{
    int n;
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b,i<<1),add(b,a,i<<1|1);
    }

    dfs(1,0);
    int res=0;
    for(int i=1;i<=k*n;i++)
        for(int d=0;d<=min(i,k);d++)Add(res,1ll*f[1][i-d][d]*i%mod);
    printf("%d",res);

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3744kb

input:

4
131 603
131 1828
1919 1828
1919 603

output:

22561

result:

wrong answer 1st numbers differ - expected: '361182910200', found: '22561'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 3908kb

input:

3
131 603
131 1828
1919 603

output:

22561

result:

wrong answer 1st numbers differ - expected: '63739309181', found: '22561'

Subtask #3:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 0ms
memory: 3936kb

input:

8
0 13
4 15
15 15
15 6
13 1
12 0
5 0
0 6

output:

0

result:

wrong answer 1st numbers differ - expected: '4047', found: '0'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%