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

Problem

Cowmpany Cowmpensation

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 other employees, each of which is assigned a direct superior. If is a superior of and is a superior of then also is a superior of . Additionally, there are no and such that is the superior of and is the superior of . Allen himself has no superior. Allen is employee number , and the others are employee numbers through .
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 and . 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 .

Input

The first line of the input contains two integers and (, ).
The remaining lines each contain a single positive integer, where the line contains the integer (). denotes the direct superior of employee .

Output

Output a single integer: the number of ways to assign salaries modulo .

Example

Input #1

1
2
3

3 2
1
1

Output #1

Input #2

1
2
3

3 3
1
2

Output #2

Input #3

1
2

2 5
1

Output #3

Note

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

标签：树形DP 多项式插值

Translation

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

Solution

不考虑数据范围，可以先想到一个的暴力做法。
令表示对于结点及其子树，的权值为时可行方案数，那么有转移方程：

用前缀和优化一下，令，那么有

最终答案为，显然复杂度会。

发现一个性质：令的子树大小为，将作为两个多项式看待，那么是一个次多项式，是一个次多项式。
这个性质可以用归纳法证明：

时，即为叶子结点时，，，满足性质
时，假设该性质对于均成立，那么对于的儿子，为一个次多项式，为一个次多项式。由于，可知为一个次多项式，即次多项式。对于每一个，都对应一个为一个次多项式，于是共有个点值，对应一个次多项式，即为一个次多项式。

由此可知，为一个次多项式，只需求得即可确定此多项式，而所求为，运用特殊多项式在整点上线性插值的方法可以在时间内求得答案。总复杂度。

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;
}