题解 子树问题
题目描述
数据范围:
n
,
k
≤
500
n,k \leq 500
n,k≤500
具体做法与心路历程
考试时想了一下，只能设出
d
p
dp
dp方程，然后不会转移。
具体做法
设
f
[
s
i
z
e
]
[
d
e
p
]
f[size][dep]
f[size][dep]表示有
s
i
z
e
size
size个节点，最大深度不超过
d
e
p
dep
dep的合法的树的数目。
考虑怎么转移
f
[
s
i
z
e
]
[
d
e
p
]
f[size][dep]
f[size][dep]:
首先有
2
2
2的父亲一定是
1
1
1,那么我们枚举以
2
2
2为根的大小i,那么除去这
i
i
i个点其余点构成一颗以
1
1
1为根，点数为
s
i
z
e
−
i
size-i
size−i,最大深度为
d
e
p
dep
dep的树。选取
2
2
2的子树中的点有
C
s
i
z
e
−
2
i
−
1
C_{size-2}^{i-1}
Csize−2i−1种方案。所以转移为:
f
[
s
i
z
e
]
[
d
e
p
]
=
∑
i
=
1
s
i
z
e
−
1
f
[
s
i
z
e
−
i
]
[
d
e
p
]
×
f
[
i
]
[
d
e
p
−
1
]
×
(
j
−
1
i
−
2
)
f[size][dep]=\sum_{i=1}^{size-1}{f[size-i][dep]\times f[i][dep-1]\times (^{i-2}_{j-1})}
f[size][dep]=i=1∑size−1f[size−i][dep]×f[i][dep−1]×(j−1i−2) 对于题目的限制条件我们把方案看成
0
0
0即可。
C
o
d
e
\mathcal{Code}
Code
#include<cstdio>
#include<algorithm>
using namespace std
;
struct IO
{
template<typename T
>
IO
& operator>>(T
&res
)
{
T q
=1;char ch
;
while((ch
=getchar())<'0' or ch
>'9')if(ch
=='-')q
=-q
;
res
=(ch
^48);
while((ch
=getchar())>='0' and ch
<='9') res
=(res
<<1)+(res
<<3)+(ch
^48);
res
*=q
;
return *this;
}
}cin
;
const int mod
=998244353;
const int maxn
=505;
long long n
,k
,fac
[maxn
],ifac
[maxn
],f
[maxn
][maxn
],l
,r
;
bool unable
[505],vis
[maxn
][maxn
];
void init()
{
fac
[0]=fac
[1]=ifac
[0]=ifac
[1]=1;
for(int i
=2;i
<=n
;i
++)
fac
[i
]=1ll*fac
[i
-1]*i
%mod
,ifac
[i
]=1ll*(mod
-mod
/i
)*ifac
[mod
%i
]%mod
;
for(int i
=2;i
<=n
;i
++)
ifac
[i
]=1ll*ifac
[i
-1]*ifac
[i
]%mod
;
}
int C(int n
,int m
)
{
return 1ll*fac
[n
]*ifac
[m
]%mod
*ifac
[n
-m
]%mod
;
}
long long dp(int size
,int dep
)
{
if(size
<=0 || dep
<=0) return 0;
if(vis
[size
][dep
]) return f
[size
][dep
];
vis
[size
][dep
]=1;
if(size
==1) return f
[size
][dep
]=1;
if(!unable
[size
-1])
f
[size
][dep
]=dp(size
-1,dep
-1);
for(int i
=1;i
<=size
-2;i
++)
if(!unable
[i
])
{
int res
=1ll*C(size
-2,i
-1)*dp(i
,dep
-1)%mod
*dp(size
-i
,dep
)%mod
;
f
[size
][dep
]=(f
[size
][dep
]+res
)%mod
;
}
return f
[size
][dep
];
}
int main()
{
cin
>>n
>>k
;
init();
for(int i
=1;i
<=k
;i
++)
{
int x
;
cin
>>x
;
unable
[x
]=1;
}
cin
>>l
>>r
;
for(int i
=l
;i
<=r
;i
++)
{
if(!unable
[n
])
printf("%lld ",(dp(n
,i
)-dp(n
,i
-1)+mod
)%mod
);
else
printf("0 ");
}
putchar('\n');
return 0;
}
