【题目描述】
兔兔和蛋蛋是一对cp,她们的国家目前正发生战乱,所以她们正在决定是否一起逃离这个国家。

该国家有$n$个城市,城市之间的道路形成一棵有向树。只能从父节点城市走到子节点城市。$1$号城市是首都,从城市$1$可以到达所有城市。每个城市都有一支军队,编号为$i$的城市其军队的攻击力为$b_i$,如果城市$i$能到达城市$j$,且$b_i > b_j$(城市 i 军队的攻击力大于城市 j 军队的攻击力),则城市$i$会向城市$j$发动$a_i$次战争。

兔兔和蛋蛋这对cp决定当战争发生次数之和多于$k$的时候一起逃离这个国家,但是他们现在不知道各个城市的攻击力$b_i$,只知道$0 \leq b_i \leq m$。她们想知道该国家发生战争次数恰好为$0, 1,\dots, k$的方案数(两个方案不同当且仅当存在一个城市$i$,$b_i$的值不同),你能帮助她们吗?

【输入格式】
第一行三个整数$n,m,k$,意义如上所述。

第二行$n$个数$a_i$,意义如上所述。

第三行$n-1$个数,第$i$个数表示第$i + 1$个城市的父节点城市编号。

【输出格式】
共$k + 1$行,第$i$行表示战争发生次数为$i-1$的方案数,答案可能很大,你只需要输出答案模$10^9 + 7$之后的值就可以了。

$0 < n \leq 14, k \leq 20, 0 \leq m \leq 100000000, 0 \leq a_i, b_i \leq m$

题解

看到$n\le 14$就八成是状压DP了

容易发现我们只关心$n$个点之间的大小关系,至于$m$的限制最后乘上组合数即可

所以我们可以考虑这样一种DP策略

开始时所有点都没有被赋值(指$b_i$) 然后我们按照值从小到大的顺序一个一个地给它们赋值 这样每次赋值的点都比之前赋了值的所有点要大(或等于) 这样的话就方便进行转移

我们设$g[i][S]$表示$S$为已赋值的点的集合 此时将$i$点赋值 会新产生多少战争

由于是按照从小到大的顺序赋值的 所以$b_i$肯定比$S$中所有点都大 所以$g[i][S]$就等于$S$中在$i$子树里的点的数目 乘$a_i$

但是还存在一个问题 万一两个点的值一样怎么办?这个其实也不难解决

我们设$f[i][j][S]$表示已赋值的点有$i$个不同的值 有$j$场战争 已赋值的点集是$S$的方案数

最外层循环是$i$然后按照dfs序来枚举一个要赋值的点$x$我们打算把$x$赋值为$i$

然后枚举加入$x$后有多少场战争以及一个包含$x$的集合$S$那么去掉$x$后就是$S_0=S-2^x$

首先$b_x$可以比之前的所有点都大 即$f[i][j][S] += f[i-1][j-g[x][S_0]][S_0]$

然后 也可能前面已经加入了值也是$i$的点 所以$f[i][j][S] += f[i][j-g[x][S_0]][S_0]$

由于我们是按照dfs序枚举的 所以第二种情况中一定没有$x$子树中的点先被赋值成$i$所以这个转移是没有问题的

最后统计答案 发动$k$次战争的方案数就是$\sum\limits_{i=1}^{n} f[i][k][2^n-1] * C(m,i)$
$C(m,i)$就是我们要从$m$个可选的值里取$i$个来用

时间复杂度$O(n^22^nk)$

更新:忘记放代码了QAQ

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return x * f;
}

const ll mod = 1000000007;
int n, m, mx;
int head[20], pre[40], to[40], sz;
int dfn[20], rnk[20], out[20], a[20], tme;
int f[15][21][(1<<15)], g[20][(1<<15)];
ll fac[20], inv[20];
//"点x"表示dfs序第x位的点
//f[i][j][k] 共有i个不同的b[x] 会发动j次战争 k为已经确定b[x]的点的状压
//g[i][k] k为已经确定b[x]的点的状压 确定b[i]会新增加多少战争

void addedge(int u, int v) {
pre[++sz] = head[u]; head[u] = sz; to[sz] = v;
pre[++sz] = head[v]; head[v] = sz; to[sz] = u;
}

ll calc(int l, int r) {
ll ret = 1;
for (int i = l; i <= r; i++) ret = ret * i % mod;
return ret;
}

inline ll C(int _n, int _m) {
return calc(_n - _m + 1, _n) * inv[_m] % mod;
}

inline ll fpow(ll x, ll t) {
ll ret = 1;
for (; t; t >>= 1, x = x * x % mod) if (t & 1) ret = ret * x % mod;
return ret;
}

void dfs(int x, int fa) { //确定dfs序
dfn[x] = ++tme; rnk[tme] = x;
for (int i = head[x]; i; i = pre[i]) {
if (to[i] != fa) dfs(to[i], x);
}
out[x] = tme;
}

int main() {
fac[0] = inv[0] = 1;
for (int i = 1; i <= 14; i++) fac[i] = fac[i-1] * i % mod;
for (int i = 1; i <= 14; i++) inv[i] = fpow(fac[i], mod - 2);
n = read(); m = read()+1; mx = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 2; i <= n; i++) {
addedge(read(), i);
}
dfs(1, 0);
for (int i = 0; i <= (1 << n) - 1; i++) {
for (int j = 1; j <= n; j++) {
int x = rnk[j];
if (!(i & (1 << (j-1)))) {
for (int k = dfn[x] + 1; k <= out[x]; k++) {
if (i & (1 << (k-1))) g[j][i] += a[x];
}
}
}
}
f[0][0][0] = 1;
for (int i = 1; i <= min(n, m); i++) { //枚举有i个不同的b[x]的取值
for (int x = 1; x <= n; x++) { //枚举要确定b[x]的值
for (int j = 0; j <= mx; j++) { //将会有j场战争
for (int k = (1 << (x-1)); k <= (1 << n) - 1; k = ((k + 1) | (1 << (x-1)))) {
//枚举一个包含j的状态压缩
int now = j - g[x][k-(1<<(x-1))]; //加入x前有now场战争
if (now < 0) continue;
f[i][j][k] = (f[i][j][k] + f[i-1][now][k-(1<<(x-1))]) % mod;
f[i][j][k] = (f[i][j][k] + f[i][now][k-(1<<(x-1))]) % mod;
}
}
}
}
for (int i = 0; i <= mx; i++) {
ll ans = 0;
for (int j = 1; j <= min(n, m); j++) {
ans = (ans + f[j][i][(1<<n)-1] * C(m, j) % mod) % mod;
}
printf("%lld\n", ans);
}
return 0;
}

评论