QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412276 | #8669. 正方形计数 | lg10 | 0 | 1ms | 3936kb | C++14 | 1.3kb | 2024-05-16 11:28:48 | 2024-05-16 11:28:49 |
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%