M_sea

CF995F Cowmpany Cowmpensation
CodeForcesLuogu分析很容易写出一个$O(nD)$的$\texttt{DP}$。设$f[i][j]$表...
扫描右侧二维码阅读全文
28
2019/01

CF995F Cowmpany Cowmpensation

CodeForces

Luogu

分析

很容易写出一个$O(nD)$的$\texttt{DP}$。

设$f[i][j]$表示以$i$为根的子树,$i$的工资是$j$的方案数。然后随便转移一下就行了。

会插值的应该都会这个DP吧

然而$D\leq 10^9$,直接$\texttt{DP}$显然不行。

观察转移方程,$f[i][j]$是一个关于$j$的$n$次多项式。

证明不会,意会一下即可

于是可以先$O(n^2)$的求出$f[1][0\sim n]$,然后套用拉格朗日插值算出$f[1][D]$。

然后,因为取值连续,所以插值可以做到$O(n\log MOD)$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline 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 n,D;
struct Edge { int v,nxt; } e[N];
int head[N],cnt=0;
int f[N][N];

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

inline void dfs(int u) { //DP
    for (re int i=1;i<=n;++i) f[u][i]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; dfs(v);
        for (re int j=1;j<=n;++j) f[u][j]=1ll*f[u][j]*f[v][j]%MOD;
    }
    for (re int i=1;i<=n;++i) f[u][i]=(f[u][i]+f[u][i-1])%MOD;
}

inline int fastpow(int a,int b,int ans=1) {
    for (;b;b>>=1,a=1ll*a*a%MOD)
        if (b&1) ans=1ll*ans*a%MOD;
    return ans;
}

inline int calc() { //插值
    if (D<=n) return f[1][D];
    int o=(n&1)?-1:1,tmp=1,ans=0;
    for (re int i=1;i<=n;++i) tmp=1ll*tmp*(D-i)%MOD;
    for (re int i=1;i<=n;++i) tmp=1ll*tmp*fastpow(i,MOD-2)%MOD;
    for (re int i=0;i<=n;++i,o=-o) {
        ans=(ans+1ll*o*f[1][i]%MOD*tmp%MOD)%MOD;
        tmp=1ll*tmp*(D-i)%MOD*fastpow(D-i-1,MOD-2)%MOD;
        tmp=1ll*tmp*(n-i)%MOD*fastpow(i+1,MOD-2)%MOD;
    }
    return (ans+MOD)%MOD;
}

int main() {
    n=read(),D=read();
    for (re int i=2;i<=n;++i) addEdge(read(),i);
    dfs(1);
    printf("%d\n",calc());
    return 0;
}
最后修改:2019 年 05 月 26 日 07 : 59 PM

3 条评论

  1. xgzc

    tql

  2. smy

    %%%插值大佬
    还有我不看翻译看不懂啊qwq

    1. M_sea
      @smy

      您在fAKe吧

发表评论