【题解】LOJ2462完美的集合(树DP 魔改Lucas)
【题解】LOJ2462完美的集合(树DP 魔改Lucas)
省选模拟考这个？？？？？？？？？？？？？？？？？？？
题目大意:
有一棵树，每个点有两个属性，一个是重量\(w_i\)一个是价值\(v_i\)。我们称一个点集\(S\)合法当且仅当
- 该集合是一个联通块\(\qquad (1)\)
- 该集合的所有点的重量和\(\le m\)，输入中给定\(m\),\(\qquad (2)\)
- 该集合的所有点的价值和是(全局)所有可能的价值和中最大的\(\qquad (3)\)
我们称一个点集的集合\(B=\{S_i\}\)合法当且仅当
- \(|B|=k\)，输入中给定\(k\),\(\qquad (4)\)
- 存在一个点\(x\)，对于所有\(S\in B\)有\(x \in S\)。\(\qquad (5)\)
- 对于上述点\(x\)，存在一个\(x\)对于所有\(S\in B\)，对于所有\(y\in S\)有\(\mathrm{dis}(x,y)\times v_y\le Max\)。输入中给定\(Max\)。\(\qquad (6)\)
请输出不同的\(B\)的个数，答案对\(5^{23}\)取模。
\(n\le 60,m\le 10000,k,w_i,v_i\le 10^9,Max\le 10^{18}\)
分两个部分解决问题因为这道题是二合一。
考虑找到所有包含\(x\)的\(S\)们。这些\(S\)的并集在树上构成了一个联通块，由于我们确定了一个\(x\)，所以每个点\(y\)是否在\((6)\)中合法是确定的，因此我们从原树上扣出一个和\(x\)联通的联通块(记为树\(T_x\))，在这个上面找到所有的\(S\)。
沿用这个博客t2的一些方法https://www.cnblogs.com/winlere/protected/p/11788856.html
外校的同学可能打不开，这里摘抄过来
定义一下二元组的运算:
\(e_1=(x_1,y_1),e_2=(x_2,y_2)\)，设\(u=\max\{x_1,x_2\}\)
\[e_1+e_2=(u,[x_1=u]y_1+[x_2=u]y_2)
\]值得注意的是这个东西满足结合律和交换律
我们枚举一个\(x\)并且令其为根，设\(dp(i,j)=(a,b)\)，表示\(i\)是\(S\)中最浅的点，\(S\)的重量和是\(j\)，且价值和是\(a\)，这样的\(S\)的方案数是\(b\)。(因为x是根，也就是当前最浅的点，所以\(dp(x,j)\)的含义就是树上所有包含\(x\)的合法的\(S\)的情况了)
二元组的运算法则和链接里面那道题是一样的。
所以我们到此满足了\((1),(2),(3),(5),(6)\)的限制，条件\((3)\)关于全局的限制可以把所有\(x\)枚举完之后得到最大值再统计答案。
考虑如何转移\(dp\)，直接树上\(DP\)的复杂度是\(O(nm^2)\)的。这是因为在儿子转移父亲的时候做了一个完全背包，但是我们实际上是01背包，然后题解给出了一个办法可以做成01背包
状态不变，转移顺序改变一下，按照\(T_x\)的dfs序的倒序转移，转移是(注意这里的加法是上面定义的!):
- 选择该dfs序的点\(dp(i,j)=dp(i,j)+ dp(i+1,j-w_{now})\)，其中\(now\)表示当前点的编号。
- 不选择该dfs序的点\(dp(i,j)=dp(i,j)+dp(i+siz[now],j)\)，\(now\)的意思同上。\(+siz[now]\)表示跳过一整个子树(因为这个点我们不选，又由于\(S\)是要和\(x\)(根)联通，所以要跳过整颗子树。这样子DP对于一个点，要么选，要么不选它的整颗子树，可以保证最终\(dp\)到根上的方案都是合法的)
这样我们就做了一个01背包了，转移只要for一个j，不需要for第二个j。复杂度\(O(nm)\)可以接受
现在我们可以得到\(h_x\)表示包含\(x\)的\(S\)的方案数。问\(B\)的方案，只要满足\((4)\)那么直接就是\(h_x\choose k\)了。
但是这里有些问题，对于一个\(B\)，可能有多个\(x\)使得它合法。设这个\(x\)的集合为\(|X|\)，一个方案我们总共算了\(|X|\)次。怎么去重?
然后题解给出一个性质
对于一个\(B\)，使得这个\(B\)合法的\(x\)的集合\(|X|\)在树上构成一个联通块
假设一条链\(1–2–3\)，\(1,3\)可以但是\(2\)不行，这种情况不可能存在
因为:
- 对于\(1\)的子树,既然\(3\)行，\(2\)为啥不行，距离还短些。
- 对于\(2\)的子树,既然\(1,3\)行为啥\(2\)不行，距离还短些。
- 对于\(3\)的子树,既然\(1\)行，\(2\)为啥不行，距离还短些。
因此\(X\)是树上一个联通块
然后由于一个联通块，点的个数=边的个数+1，因此去重就有思路了，设\(h_{e=(a,b)}\)表示必须\(ab\)点都是可以作为\(x\)的所有合法的\(S\)的个数，求\(h_e\)的方法和\(h_x\)一样，扣出来的树是\(T_a\cap T_b\)，按dfs倒序转移的时候判断下\(now==i\)，如果是这样就强制转移”选择”的情况。
那么答案就是
\]
这样对于一个\(B\)，我们算了\(|X|-(|X|-1)=1\)次。
到这里复杂度\(O(n^2m)\)
二合一的第一部分完结，现在问题就是求一个组合数。。。。
显然\(h\le 2^{60}\)拿long long存下，现在要求一个\(n,m\)都很大的组合数，模\(5^{23}\)。
考虑exLucas。这里只需要求\(p^i\)下的组合数，然而\(exLucas\)是\(O(p^i)\)的，搞不得。
然而考虑这里的瓶颈是啥，其实是求\(g(n)\)的时候我们是暴力求循环节\(O(p^i)\)，然后给出一个不暴力的做法….
搞个生成函数
\]
所以\(g(n)=f_n(0)\)。
然后考虑\(f\)的倍增…
\]
对于\(f_{5k}(x)\)，\(x^{>23}\)次都是无意义的，因为系数都有一个\(5^{23}\)。而最终我们只需要求\(f_{n}(0)\)(也就是常数项)，所以对于任何\(f_{t}(x)\)，我们只需要保留前\(24\)项。
求那么\(f_{10k}\)可以递归到\(f_{5k}\)，问题规模缩小了一半。问题是\(f_{5k}(x)\)不一定能递归下去，其实只要递归到\(\le 5k\)最近的\(10\)的倍数即可，再暴力乘上最多\(9\)项形如\((x+i)\)的式子。处理\(f_n(x)\)也是同样的办法。
因为多项式长度是常数(24)，所以复杂度是\(T(n)=T(n/2)+\text{不大不小的常数}=O(\text{不大不小的常数}\log n)\)
什么叫二合一啊(战术仰头)
代码:(爷抄的std，不要看了)
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pll;
const lint mod = 11920928955078125, phi = mod / 5 * 4;
const int maxn = 65, maxm = 10005, maxd = 25;
int n, m, k, w[maxn], v[maxn];
lint Max, lim, ans;
int dis[maxn][maxn], fa[maxn];
inline lint gi() {
char c = getchar();
while (c < '0' || c > '9')
c = getchar();
lint sum = 0;
while ('0' <= c && c <= '9')
sum = sum * 10 + c - 48, c = getchar();
return sum;
}
inline lint inc(lint a, lint b) { return a + b >= mod ? a + b - mod : a + b; }
inline lint mul(lint a, lint b) { return (__int128)a * b % mod; }
inline lint fpow(lint x, lint k) {
lint res = 1;
while (k) {
if (k & 1)
res = mul(res, x);
x = mul(x, x);
k >>= 1;
}
return res;
}
inline lint inv(lint x) { return fpow(x, phi - 1); }
namespace Binom {
lint C[maxd][maxd], pw[maxd];
struct poly {
lint a[maxd];
poly() { memset(a, 0, sizeof(a)); }
poly(lint d) {
memset(a, 0, sizeof(a));
a[1] = 1;
a[0] = d;
}
friend inline poly operator*(const poly &a, const poly &b) {
poly c;
for (int i = 0; i <= 23; ++i)
if (b.a[i])
for (int j = 0; i + j <= 23; ++j)
c.a[i + j] = inc(c.a[i + j], mul(a.a[j], b.a[i]));
return c;
}
void extend(lint k) {
pw[0] = 1;
for (int i = 1; i <= 23; ++i)
pw[i] = mul(pw[i - 1], k);
for (int i = 0; i <= 23; ++i) {
lint res = 0;
for (int j = i; j <= 23; ++j)
res = inc(res, mul(a[j], mul(C[j][i], pw[j - i])));
a[i] = res;
}
}
} pre[10005];
void prepare() {
C[0][0] = 1;
for (int i = 1; i <= 23; ++i) {
C[i][0] = 1;
for (int j = 1; j <= 23; ++j)
C[i][j] = inc(C[i - 1][j - 1], C[i - 1][j]);
}
pre[0].a[0] = 1;
for (int i = 1; i <= 10000; ++i)
if (i % 5)
pre[i] = pre[i - 1] * poly(i);
else
pre[i] = pre[i - 1];
}
inline poly getpoly(lint n) {
if (n <= 10000)
return pre[n];
lint k = n / 10 * 10;
poly t1 = getpoly(k >> 1), t2 = t1;
t2.extend(k >> 1);
t2 = t1 * t2;
for (lint i = k + 1; i <= n; ++i)
if (i % 5)
t2 = t2 * poly(i);
return t2;
}
inline pll calc(lint n) {
poly t = getpoly(n);
lint res = n / 5;
if (res > 0) {
pll t2 = calc(n / 5);
t.a[0] = mul(t.a[0], t2.first);
res = inc(res, t2.second);
}
return make_pair(t.a[0], res);
}
inline lint binom(lint n) {
if (n < k)
return 0;
pll t1 = calc(n), t2 = calc(n - k), t3 = calc(k);
t1.second -= (t2.second + t3.second);
if (t1.second >= 23)
return 0;
t1.first =
mul(t1.first, mul(fpow(5, t1.second), inv(mul(t2.first, t3.first))));
return t1.first;
}
} // namespace Binom
namespace tree {
struct edge {
int to, next, w;
} e[maxn * 2];
int h[maxn], tot;
int valid[maxn], id[maxn], siz[maxn], cnt;
lint f[maxn][maxm], g[maxn][maxm];
inline void add(int u, int v, int w) {
e[++tot] = (edge){v, h[u], w};
h[u] = tot;
e[++tot] = (edge){u, h[v], w};
h[v] = tot;
}
void dfs_pre(int rt, int u, int f) {
fa[u] = f;
for (int i = h[u], v; v = e[i].to, i; i = e[i].next)
if (v != f) {
dis[rt][v] = dis[rt][u] + e[i].w;
dfs_pre(rt, v, u);
}
}
void dfs(int u, int fa) {
id[++cnt] = u;
siz[u] = 1;
for (int i = h[u], v; v = e[i].to, i; i = e[i].next)
if (v != fa && valid[v])
dfs(v, u), siz[u] += siz[v];
}
pll calc(int x, int y) {
cnt = 0;
dfs(x, 0);
for (int i = 0; i <= m; ++i)
f[cnt + 1][i] = 0, g[cnt + 1][i] = 1;
for (int u, i = cnt; i >= 1; --i) {
u = id[i];
for (int j = 0; j <= m; ++j) {
if (y == u && j < w[u]) {
f[i][j] = g[i][j] = 0;
} else if (y == u ||
(j >= w[u] && f[i + siz[u]][j] < f[i + 1][j - w[u]] + v[u])) {
f[i][j] = f[i + 1][j - w[u]] + v[u];
g[i][j] = g[i + 1][j - w[u]];
} else if (j < w[u] || f[i + siz[u]][j] > f[i + 1][j - w[u]] + v[u]) {
f[i][j] = f[i + siz[u]][j];
g[i][j] = g[i + siz[u]][j];
} else {
f[i][j] = f[i + siz[u]][j];
g[i][j] = g[i + siz[u]][j] + g[i + 1][j - w[u]];
}
}
}
return make_pair(f[1][m], g[1][m]);
}
} // namespace tree
lint solve(int a, int b) {
for (int i = 1; i <= n; ++i)
if ((lint)dis[a][i] * v[i] <= Max && (lint)dis[b][i] * v[i] <= Max)
tree::valid[i] = 1;
else
tree::valid[i] = 0;
if (!tree::valid[a] || !(tree::valid[b] || (!b)))
return 0;
pll t = tree::calc(a, b);
if (t.first != lim)
return 0;
return Binom::binom(t.second);
}
int main() {
freopen("yukinoshita_yukino.in", "r", stdin);
freopen("yukinoshita_yukino.out", "w", stdout);
n = gi();
m = gi();
k = gi();
Max = gi();
Binom::prepare();
for (int i = 1; i <= n; ++i)
w[i] = gi();
for (int i = 1; i <= n; ++i)
v[i] = gi();
for (int u, v, w, i = 1; i < n; ++i) {
u = gi();
v = gi();
w = gi();
tree::add(u, v, w);
}
for (int i = n; i >= 1; --i)
tree::dfs_pre(i, i, 0);
for (int i = 1; i <= n; ++i)
tree::valid[i] = 1;
for (int i = 1; i <= n; ++i)
lim = max(lim, tree::calc(i, 0).first);
if (!lim)
return puts("0"), 0;
for (int i = 1; i <= n; ++i)
ans = inc(ans, solve(i, 0) - (fa[i] ? solve(i, fa[i]) : 0));
printf("%lld\n", ans);
return 0;
}