[2021.4.9多校省选模拟35]隐形斗篷 （prufer序列，背包DP）
题面
我编不下去了！
给出
n
n
n 个点，第
i
i
i 个点的度数限制为
a
i
a_i
ai，现在需要选出
x
x
x 个点构成一颗树，要求这
x
x
x 个点中每个点的度数不超过这个点的
a
i
a_i
ai 值，求
x
=
1
,
2
,
…
,
n
x=1,2,\ldots,n
x=1,2,…,n 时的方案数。
两种方案不同，当且仅当选出的点集不同或者连边的方式不同。
输入格式
第一行一个正整数
T
T
T，代表有
T
T
T 组数据。每组数据第一行一个正整数
n
n
n
第二行
n
n
n 个正整数
a
1
,
a
2
,
…
,
a
n
a_1,a_2,\ldots,a_n
a1,a2,…,an。
输出格式
对于每组数据，输出一行
n
n
n 个数，表示
x
=
1
,
2
,
…
,
n
x=1,2,\ldots,n
x=1,2,…,n 时的答案对
1000000007
1000000007
1000000007 取模后的结果。
样例输入
1
3
2 2 1样例输出
3 3 2数据范围与提示
本题共
10
10
10 组测试点。
对于第
i
i
i 个测试点，
1
≤
n
≤
5
i
,
1
≤
T
≤
10
,
1
≤
a
1
,
a
2
,
…
,
a
n
≤
n
1\leq n\leq 5i,1\leq T\leq 10,1\leq a_1,a_2,\ldots,a_n\leq n
1≤n≤5i,1≤T≤10,1≤a1,a2,…,an≤n。
总的来说，
1
≤
n
≤
50
1\leq n\leq 50
1≤n≤50。
题解
根据 p
[
r
u
f
e
r
\rm prufer
](https://blog.csdn.net/qq_42101694/article/details/103151094)
prufer 序列的知识，我们可以发现，当
x
=
k
x=k
x=k，选的点集为
{
p
1
,
p
2
,
…
,
p
k
}
\{p_1,p_2,\ldots,p_k\}
{p1,p2,…,pk} 时，答案为：
∑
i
1
=
1
a
p
1
∑
i
2
=
1
a
p
2
.
.
.
∑
i
k
=
1
a
p
k
(
k
−
2
)
!
(
i
1
−
1
)
!
(
i
2
−
1
)
!
.
.
.
(
i
k
−
1
)
!
[
∑
i
=
(
k
−
1
)
∗
2
]
\sum_{i_1=1}^{a_{p_1}}\sum_{i_2=1}^{a_{p_2}}…\sum_{i_k=1}^{a_{p_k}}\frac{(k-2)!}{(i_1-1)!(i_2-1)!…(i_k-1)!}[\sum i=(k-1)*2]
i1=1∑ap1i2=1∑ap2…ik=1∑apk(i1−1)!(i2−1)!…(ik−1)!(k−2)![∑i=(k−1)∗2]
看来思路已经很清晰了，但是现在暴力能拿
10
10
10 分吗？不好说。
考虑把这个式子拆开：
(
k
−
2
)
!
∑
i
1
=
1
a
p
1
∑
i
2
=
1
a
p
2
.
.
.
∑
i
k
=
1
a
p
k
1
(
i
1
−
1
)
!
(
i
2
−
1
)
!
.
.
.
(
i
k
−
1
)
!
[
∑
i
=
(
k
−
1
)
∗
2
]
(k-2)!\sum_{i_1=1}^{a_{p_1}}\sum_{i_2=1}^{a_{p_2}}…\sum_{i_k=1}^{a_{p_k}}\frac{1}{(i_1-1)!(i_2-1)!…(i_k-1)!}[\sum i=(k-1)*2]
(k−2)!i1=1∑ap1i2=1∑ap2…ik=1∑apk(i1−1)!(i2−1)!…(ik−1)!1[∑i=(k−1)∗2]
右边那个大分式似乎有些头绪了？这不就相当于 "
k
k
k 个物品，每个物品有
a
p
i
a_{p_i}
api 种，选
x
x
x 个的权值为
1
(
x
−
1
)
!
\frac{1}{(x-1)!}
(x−1)!1 ，背包大小为
(
k
−
1
)
∗
2
(k-1)*2
(k−1)∗2 ，问刚好塞满时每种情况权值积的和 "？
所以就是个裸的背包DP了，令
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 为选了
i
i
i 种物品，背包已用空间为
j
j
j 时的权值积的和，那么类似分组背包问题求解就完了。最终
x
=
k
x=k
x=k 时的答案就是
(
k
−
2
)
!
∗
d
p
[
k
]
[
(
k
−
1
)
∗
2
]
(k-2)!*dp[k][(k-1)*2]
(k−2)!∗dp[k][(k−1)∗2]，复杂度
O
(
T
n
4
)
O(Tn^4)
O(Tn4) 。
CODE
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 55
#define LL long long
#define DB double
#define ENDL putchar('\n')
#define lowbit(x) (-(x) & (x))
LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s == '-')f=-f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
const int MOD = 1000000007;
int n,m,i,j,s,o,k;
inline void MD(int &x) {if(x>=MOD)x-=MOD;}
int a[MAXN];
int dp[MAXN][MAXN<<1];
int fac[MAXN],inv[MAXN],invf[MAXN];
int main() {
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
int T = read();
fac[1] = fac[0] = inv[1] = inv[0] = invf[1] = invf[0] = 1;
for(int i = 2;i <= 50;i ++) {
fac[i] = fac[i-1] *1ll* i % MOD;
inv[i] = (MOD-inv[MOD % i]) *1ll* (MOD/i) % MOD;
invf[i] = invf[i-1] *1ll* inv[i] % MOD;
}
while(T --) {
n = read();
for(int i = 1;i <= n;i ++) a[i] = read();
memset(dp,0,sizeof(dp));
dp[0][0] = 1;
int du = (n-1)*2;
for(int i = 1;i <= n;i ++) {
for(int ct = n;ct > 0;ct --) {
for(int j = du;j >= 1;j --) {
for(int x = 1;x <= j && x <= a[i];x ++) {
MD(dp[ct][j] += dp[ct-1][j-x] *1ll* invf[x-1] % MOD);
}
}
}
}
for(int k = 1;k <= n;k ++) {
if(k == 1) {printf("%d ",n);continue;}
if(k == 2) {printf("%lld ",n*1ll*(n-1) % MOD *1ll* inv[2] % MOD);continue;}
int ans = dp[k][(k-1)*2] *1ll* fac[k-2] % MOD;
printf("%d ",ans);
}
ENDL;
}
return 0;
}手机扫一扫
移动阅读更方便
你可能感兴趣的文章