CF995F Cowmpany Cowmpensation < 树形DP+多项式插值 >

Problem

Cowmpany Cowmpensation

$\mathrm{Time\;Limit:\;2\;seconds}$
$\mathrm{Memory\;Limit:\;256\;megabytes}$

Description

Allen, having graduated from the MOO Institute of Techcowlogy (MIT), has started a startup! Allen is the president of his startup. He also hires $n-1$ other employees, each of which is assigned a direct superior. If $u$ is a superior of $v$ and $v$ is a superior of $w$ then also $u$ is a superior of $w$. Additionally, there are no $u$ and $v$ such that $u$ is the superior of $v$ and $v$ is the superior of $u$. Allen himself has no superior. Allen is employee number $1$, and the others are employee numbers $2$ through $n$.
Finally, Allen must assign salaries to each employee in the company including himself. Due to budget constraints, each employee’s salary is an integer between $1$ and $D$. Additionally, no employee can make strictly more than his superior.
Help Allen find the number of ways to assign salaries. As this number may be large, output it modulo $10^9+7$.

Input

The first line of the input contains two integers $n$ and $D$ ($1\le n\le3000$, $1\le D\le10^9$).
The remaining $n-1$ lines each contain a single positive integer, where the $i^{th}$ line contains the integer $p_i$ ($1\le p_i\le i$). $p_i$ denotes the direct superior of employee $i+1$.

Output

Output a single integer: the number of ways to assign salaries modulo $10^9+7$.

Example

Input #1

3 2
1
1

Output #1

5

Input #2

3 3
1
2

Output #2

10

Input #3

2 5
1

Output #3

15

Note

In the first sample case, employee $2$ and $3$ report directly to Allen. The three salaries, in order, can be $(1,1,1)$, $(2,1,1)$, $(2,1,2)$, $(2,2,1)$ or $(2,2,2)$.
In the second sample case, employee $2$ reports to Allen and employee $3$ reports to employee $2$. In order, the possible salaries are $(1,1,1)$, $(2,1,1)$, $(2,2,1)$, $(2,2,2)$, $(3,1,1)$, $(3,2,1)$, $(3,2,2)$, $(3,3,1)$, $(3,3,2)$, $(3,3,3)$.

标签：树形DP 多项式插值

Translation

题目大意：给定一棵根为$1$的树，需要给每个结点一个权值，使得父亲的权值不小于儿子的权值，并且所有权值均不大于$D$。求可行方案数并输出其模$10^9+7$的值。

Solution

不考虑数据范围，可以先想到一个$O(nD)$的暴力$\mathrm{DP}$做法。
令$f[u][i]$表示对于结点$u$及其子树，$i$的权值为$u$时可行方案数，那么有转移方程：

$$f[u][i]=\prod_{（u\to v）\in E}\sum_{j\le i}f[v][j]$$

用前缀和优化一下，令$g[u][i]=\sum_{j=0}^{i}f[u][j]$，那么有

$$f[u][i]=\prod_{（u\to v）\in E}g[v][i]$$

最终答案为$g[1][D]$，显然复杂度$O(nD)$会$\mathrm{TLE}$。

发现一个性质：令$x$的子树大小为$sz_x$，将$f[x][],g[x][]$作为两个多项式$f_x,g_x$看待，那么$f_u$是一个$sz_u-1$次多项式，$g_u$是一个$sz_u$次多项式。
这个性质可以用归纳法证明：

• $sz_u=1$时，即$u$为叶子结点时，$f_u(x)=1$，$g_u(x)=x$，满足性质
• $sz_u>1$时，假设该性质对于$1\sim(sz_u-1)$均成立，那么对于$u$的儿子$v$，$f_v$为一个$sz_v-1$次多项式，$g_v$为一个$sz_v$次多项式。由于$f_u(x)=\prod_{(u\to v)\in E}g_v(x)$，可知$f_u$为一个$\sum sz_v$次多项式，即$sz_u-1$次多项式。对于每一个$x\in[0,sz_u]$，都对应一个$f_u(x)$为一个$sz_u-1$次多项式，于是共有$sz_u+1$个点值，对应一个$sz_u$次多项式，即$g_u$为一个$sz_u$次多项式。

由此可知，$g_1$为一个$n$次多项式，只需求得$g_1(0)\sim g_1(n)$即可确定此多项式，而所求为$g_1(D)$，运用特殊多项式在整点上线性插值的方法可以在$O(n)$时间内求得答案。总复杂度$O(n^2+n)$。

Code

#include <bits/stdc++.h>
#define MAX_N 3000
#define P 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;
vector <int> G[MAX_N+5];
lnt f[MAX_N+5][MAX_N+5];
lnt fac[MAX_N+5], inv[MAX_N+5];
void init(int n) {
    fac[0] = inv[0] = inv[1] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i-1]*i%P;
    for (int i = 2; i <= n; i++) inv[i] = (P-P/i*inv[P%i]%P)%P;
    for (int i = 2; i <= n; i++) inv[i] = inv[i]*inv[i-1]%P;
}
void DFS(int u) {
    for (int x = 1; x <= n; x++) f[u][x] = 1;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i]; DFS(v);
        for (int x = 1; x <= n; x++)
            f[u][x] = f[u][x]*f[v][x]%P;
    }
    for (int x = 1; x <= n; x++)
        f[u][x] = (f[u][x]+f[u][x-1])%P;
}
#define getL(i) (i < n ? pre[n-i-1] : 1)
#define getR(i) (i > 0 ? suc[n-i+1] : 1)
lnt Poly_Inter() {
    lnt ret = 0;
    lnt pre[MAX_N+5], suc[MAX_N+5]; pre[0] = m-n, suc[n] = m;
    for (int i = 1; i <= n-1; i++) pre[i] = pre[i-1]*(m-n+i)%P;
    for (int i = n-1; i >= 1; i--) suc[i] = suc[i+1]*(m-n+i)%P;
    for (int i = 0, c = (n&1) ? -1 : 1; i <= n; i++, c = -c)
        ret = (ret+c*getL(i)*getR(i)%P*inv[i]%P*inv[n-i]%P*f[1][i]%P)%P;
    return (ret+P)%P;
}
int main() {
    read(n), read(m), init(n);
    for (int i = 2, x; i <= n; i++)
        read(x), G[x].push_back(i);
    DFS(1), printf("%lld\n", Poly_Inter());
    return 0;
}