什么是速成网站,制作网站的固定成本,网站开发课题开发背景,前端网站开发流程F. Cowmpany Cowmpensation
首先一般dp推导dp[i][j]∏u∈soni∑k1jdp[v][k]dp[i][j] \prod\limits_{u \in son_i} \sum\limits_{k 1} ^{j} dp[v][k]dp[i][j]u∈soni∏k1∑jdp[v][k]
这个是毫无疑问的#xff0c;然后我们考虑如何得到d≥nd \geq nd≥n的情况。
我们…F. Cowmpany Cowmpensation
首先一般dp推导dp[i][j]∏u∈soni∑k1jdp[v][k]dp[i][j] \prod\limits_{u \in son_i} \sum\limits_{k 1} ^{j} dp[v][k]dp[i][j]u∈soni∏k1∑jdp[v][k]
这个是毫无疑问的然后我们考虑如何得到d≥nd \geq nd≥n的情况。
我们给定一个出了1号节点全是叶节点的情况显然在根节点的统计也就是一个关于叶节点个数的多项式当我们对根节点的情况统计求和的时候这个维度可能会升高所以得到在这种情况下最多就是n次多项式
其他情况类比上面的情况得到这是一个最多为n次的多项式所以我们筛出前n 1项来就能套上拉个朗日插值了
dfsdfsdfs进行dpdpdp的复杂度是O(n2)O(n ^ 2)O(n2)的加上O(n)O(n)O(n)拉格朗日插值整体还是O(n2)O(n ^ 2)O(n2)得。
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.husing namespace std;typedef long long ll;const int inf 0x3f3f3f3f;
const double eps 1e-7;const int N 3e3 10, mod 1e9 7;int head[N], to[N], nex[N], cnt 1, n, d;ll dp[N][N], pre[N], suc[N], fac[N], inv[N];ll quick_pow(ll a, int n) {ll ans 1;while(n) {if(n 1) ans ans * a % mod;a a * a % mod;n 1;}return ans;
}void add(int x, int y) {to[cnt] y;nex[cnt] head[x];head[x] cnt;
}void dfs(int rt, int fa) {for(int i 1; i n 1; i) dp[rt][i] 1;for(int i head[rt]; i; i nex[i]) {if(to[i] fa) continue;dfs(to[i], rt);for(int j 1; j n 1; j) {dp[rt][j] (1ll * dp[rt][j] * dp[to[i]][j]) % mod;}}for(int i 1; i n 1; i) dp[rt][i] (dp[rt][i] dp[rt][i - 1]) % mod;
}ll solve(int x) {if(x n 1) return dp[1][x];n;pre[0] suc[n 1] fac[0] inv[0] 1;for(int i 1; i n; i) {pre[i] 1ll * pre[i - 1] * (x - i) % mod;fac[i] 1ll * fac[i - 1] * i % mod;}fac[n 1] 1ll * fac[n] * (n 1) % mod;inv[n 1] quick_pow(fac[n 1], mod - 2);for(int i n; i 1; i--) {suc[i] 1ll * suc[i 1] * (x - i) % mod;inv[i] 1ll * inv[i 1] * (i 1) % mod;}ll ans 0;for(int i 1; i n; i) {ll a 1ll * pre[i - 1] * suc[i 1] % mod * dp[1][i] % mod;ll b 1ll * inv[i - 1] * inv[n - i] % mod;if((n - i) 1) b * -1;ans ((ans a * b % mod) % mod mod) % mod;}return ans;
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf(%d %d, n, d);for(int i 2; i n; i) {int x; scanf(%d, x);add(x, i);}dfs(1, 0);printf(%lld\n, solve(d));return 0;
}
