ABC459E Select from Subtrees
题目大意
给你一棵有 n 个节点的树,1 号点为根节点,每个节点有 ci 个糖果(所有糖果不互相同),且有一只松鼠,它需要在这颗子树中选出 di 个糖果,两种方案互不相同当且仅当选出的糖果或拿糖果的松鼠不同,求方案数。
数据范围:2≤n≤2×105,1≤ci≤109,∑di≤106。
题解
很明显的树形 DP,考虑 fu 为当前子树答案。
令 sdu 为子树 u 中 di 之和,scu 同理,对于所有子节点 vi,有:
fu=(duscu−sdu+du)×∏fv
可以理解为从选剩下的糖果中再选 du 个。
此时有一个问题,左边的组合数怎么算?cu 是 109 级别的,scu 就能达到 1014,考虑把它拆开:
(duscu−sdu+du)=(scu−sdu)!×du!(scu−sdu+du)!
题目条件中有一个 ∑di≤106,结合上面的阶乘,容易发现括号中只有 du 项,完全可以现场跑一遍,至于 du!1,预处理即可。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 2e5+10 , D = 1e6+10;
const int MOD = 998244353;
int n;
int h[N] , e[N] , ne[N] , idx;
LL c[N] , d[N] , sc[N] , sd[N];
LL fac[D] , inv[D];
LL f[N];
void add(int a , int b) {
e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}
LL qmi(LL a , LL b) {
LL res = 1;
while(b) {
if(b & 1) res = res*a%MOD;
a = a*a%MOD; b >>= 1;
}
return res;
}
void dfs(int u) {
sc[u] += c[u];
sd[u] += d[u];
f[u] = 1;
for(int i = h[u] ; ~i ; i = ne[i]) {
int v = e[i];
dfs(v);
sc[u] += sc[v];
sd[u] += sd[v];
f[u] = f[u]*f[v]%MOD;
}
if(d[u] <= sc[u]-sd[u]+d[u]) {
for(LL x = sc[u]-sd[u]+1 ; x <= sc[u]-sd[u]+d[u] ; x ++)
f[u] = f[u]*(x%MOD)%MOD;
f[u] = f[u]*inv[d[u]]%MOD;
} else f[u] = 0;
}
int main() {
scanf("%d" , &n);
memset(h , -1 , sizeof h);
for(int v = 2 ; v <= n ; v ++) {
int u; scanf("%d" , &u);
add(u , v);
}
int maxd = 0;
for(int i = 1 ; i <= n ; i ++) scanf("%lld" , &c[i]);
for(int i = 1 ; i <= n ; i ++)
scanf("%lld" , &d[i]) , maxd = max(maxd , (int)d[i]);
fac[0] = 1;
for(int i = 1 ; i <= maxd ; i ++)
fac[i] = fac[i-1]*i % MOD;
inv[maxd] = qmi(fac[maxd] , MOD-2);
for(int i = maxd-1 ; i >= 0 ; i --)
inv[i] = inv[i+1]*(i+1)%MOD;
dfs(1);
printf("%lld\n" , f[1]);
return 0;
}一个取模没写调了半个多小时
