CF995F Cowmpany Cowmpensation

CF995F Cowmpany Cowmpensation

题意

给定一棵树，你要给每个点定一个 [ 1 , D ] [1,D] [1,D] 的权值，满足每个点权值不大于父亲。问有多少种方案，答案模 1 0 9 + 7 10^9 + 7 109+7

题解

首先考虑一个暴力的DP
f [ u ] [ i ] 表 示 以 u 为 根 的 子 树 ， 用 [ 1 , i ] 染 色 的 方 案 数 f[u][i]表示以u为根的子树，用[1,i]染色的方案数 f[u][i]表示以u为根的子树，用[1,i]染色的方案数

显 然 f [ u ] [ i ] = f [ u ] [ i − 1 ] + ∏ f [ v ] [ i ] 显然f[u][i]=f[u][i-1]+\prod f[v][i] 显然f[u][i]=f[u][i−1]+∏f[v][i]

时间复杂度是 O ( n D ) O(nD) O(nD)的，直接去世
发现D这么大，盲猜是个多项式
然鹅确实是的
f [ u ] [ i ] 是 关 于 i 的 s i z e [ u ] 次 多 项 式 f[u][i]是关于i的size[u]次多项式 f[u][i]是关于i的size[u]次多项式
所以只需要把 f [ 1 ] [ 1   n + 1 ] f[1][1~n+1] f[1][1 n+1]求出来，然后就可以唯一确定这个多项式
直接插值即可
code:

#include<bits/stdc++.h>
#define N 1000005
#define int long long
#define mod 1000000007
using namespace std;
int qpow(int x, int y) {
	int ret = 1;
	for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
	return ret;
}
int t, n, m, k, x[N], y[N], fac[N], pre[N], suf[N], a[N], dp[3005][3005];
int lagrange(int k) {//大力插值

	fac[0] = pre[0] = suf[n + 1] = 1;
	for(int i = 1; i <= n; i ++) fac[i] = fac[i - 1] * i % mod, pre[i] = pre[i - 1] * (k - x[i] + mod)% mod;
	for(int i = n; i >= 1; i --) suf[i] = suf[i + 1] * (k - x[i] + mod) % mod;
	
	int ans = 0;
	for(int i = 1; i <= n; i ++) {
		int pi = pre[x[i] - 1] * suf[x[i] + 1] % mod;
		int ha = fac[x[i] - 1] * fac[n - x[i]] % mod; 
		if((n - i) & 1) ha = (mod - ha) % mod;
		pi = pi * qpow(ha, mod - 2) % mod;
		ans = (ans + y[i] * pi % mod) % mod;
	}
	return ans; 
}
struct edge {
	int v, nxt;
} e[N << 1];
int p[N], eid;
void init() {
	memset(p, -1, sizeof p);
	eid = 0;
}
void insert(int u, int v) {
	e[eid].v = v;
	e[eid].nxt = p[u];
	p[u] = eid ++;
}
void dfs(int u, int fa) {//直接n^2  DP
	for(int i = 1; i <= n; i ++) dp[u][i] = 1;
	for(int i = p[u]; i + 1; i = e[i].nxt) {
		int v = e[i].v;
		if(v == fa) continue;
		dfs(v, u);
		for(int j = 1; j <= n; j ++) dp[u][j] = dp[u][j] * dp[v][j] % mod;		
	}
	for(int i = 2; i <= n; i ++) dp[u][i] = (dp[u][i] + dp[u][i - 1]) % mod;
}
signed main() {
	init();
	scanf("%lld%lld", &n, &m);
	for(int i = 2; i <= n; i ++) {
		int u = i, v = 0;
		scanf("%d", &v);
		insert(u, v);
		insert(v, u);
	}
	n ++;
	dfs(1, 1);
	for(int i = 1; i <= n; i ++) 
		x[i] = i, y[i] = dp[1][i];
	printf("%lld\n", lagrange(m));	
	return 0;
}