CodeForces

Luogu

分析

设 $dp_{i,j}$ 表示以 $i$ 为根的子树，$i$ 的权值为 $j$ 的方案数。容易得到转移
$$
dp_{i,j}=\prod_{v\in son_i}\sum_{k=1}^jdp_{v,k}
$$
前缀和优化即可做到 $\mathcal{O}(D)$ 转移，总时间复杂度 $\mathcal{O}(nD)$。

考虑优化。可以发现，$dp_{1,x}$ 为关于 $x$ 的 $n$ 次多项式（可以理解为每个叶子节点都为一次式，往上合并时做乘法从而次数上升）。

那么我们只需要求出 $dp_{1,1..n}$ 然后拉格朗日插值即可。时间复杂度 $\mathcal{O}(n^2)$。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=3000+10;
const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,D,dp[N][N];

struct edge { int v,nxt; } e[N];
int head[N];
void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

void dfs(int u) {
    for (int i=1;i<=n;++i) dp[u][i]=1;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; dfs(v);
        for (int j=1;j<=n;++j)
            dp[u][j]=1ll*dp[u][j]*dp[v][j]%mod;
    }
    for (int i=1;i<=n;++i) dp[u][i]=(dp[u][i]+dp[u][i-1])%mod;
}

int calc(int x) {
    if (x<=n) return dp[1][x];
    int s=1,res=0,o=n&1?mod-1:1;
    for (int i=1;i<=n;++i) s=1ll*s*(x-i)%mod*qpow(i,mod-2)%mod;
    for (int i=0;i<=n;++i,o=mod-o) {
        res=(res+1ll*dp[1][i]*o%mod*s)%mod;
        s=1ll*s*(x-i)%mod*qpow(x-i-1,mod-2)%mod*qpow(i+1,mod-2)%mod*(n-i)%mod;
    }
    return res;
}

int main() {
    n=read(),D=read();
    for (int i=2;i<=n;++i) addEdge(read(),i);
    dfs(1); printf("%d\n",calc(D));
    return 0;
}
最后修改：2021 年 03 月 24 日 05 : 08 PM
© 允许规范转载