【题目描述】
该国家有$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$个数$a_i$，意义如上所述。
第三行$n-1$个数，第$i$个数表示第$i + 1$个城市的父节点城市编号。
【输出格式】
$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)$
时间复杂度$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 ]; 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) 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++) { for (int x = 1 ; x <= n; x++) { for (int j = 0 ; j <= mx; j++) { for (int k = (1 << (x-1 )); k <= (1 << n) - 1 ; k = ((k + 1 ) | (1 << (x-1 )))) { int now = j - g[x][k-(1 <<(x-1 ))]; 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 ; }
