洛谷P5206 [WC2019] 数树(数学)
题目描述
本题包含三个问题:
- 问题 0:已知两棵 (n) 个节点的树的形态(两棵树的节点标号均为 (1) 至 (n)),其中第一棵树是红树,第二棵树是蓝树。要给予每个节点一个 ([1, y]) 中的整数,使得对于任意两个节点 (p, q),如果存在一条路径 ((a_1 = p, a_2, cdots , a_m = q)) 同时属于这两棵树,则 (p, q) 必须被给予相同的数。求给予数的方案数。
- 存在一条路径同时属于这两棵树的定义见「题目背景」。
- 问题 1:已知蓝树,对于红树的所有 (n^{n-2}) 种选择方案,求问题 0 的答案之和。
- 问题 2:对于蓝树的所有 (n^{n-2}) 种选择方案,求问题 1 的答案之和。
提示:(n) 个节点的树一共有 (n^{n-2}) 种。
在不同的测试点中,你将可能需要回答不同的问题。我们将用 ( ext{op}) 来指代你需要回答的问题编号(对应上述 0、 1、 2)。
由于答案可能很大,因此你只需要输出答案对 (998, 244, 353) 取模的结果即可。
数据范围
$ 1 le n le 10^5 $
解题思路
这题是一道熟练题,但也得熟练到一定程度才能很快的切掉吧
attention 下面我用 (y_r) 代表 (frac 1y)
subtask1:两棵树都给出
很简单吧,直接 set 看看两棵树相同边集的大小
答案就是
subtask2:给出第一棵树
答案是
前面枚举并集,然后 (prufer) 序列计数,每个联通块可以随便选出来一个点连边,(k) 指的是联通块个数 = (n-|E|),(siz) 指的是联通块大小
继续
其实直接从组合意义理解也是可以的,就是 (prufer) 序列其实填 (n) 个数中的任意一个都可以
发现集合的并恰好等于很难办,设
有
这里给出另一种顺推做法
因此有
考虑后面暴力 (dp),(dp[i][j]) 表示当前节点为 (i),当前联通块大小为 (j) 的方案数,走出去的时候把 (siz) 乘上即可
用组合一样可以做到更优的 (Theta(n)) 做法,问题等价于把树分成若干的联通块,每个块中选出一个点的方案数,因此我们设 (dp[i][0/1]) 表示当前节点为 i,当前联通块有没有选择关键点即可
具体的 (dp) 转移方程
subtask3:一棵树也不给
由上一问可知
推法一:大力推式子,枚举有几个联通块
这题到底要多熟练啊!
推法二:生成函数熟练者使用
下面是组合意义,可以从联通块的角度考虑,一个联通块对乘积的贡献是 (siz_i^2n^2(y_r-1)^{-1}),又因为一个联通块有 (siz_i^{siz_i-2}) 种生成树,所以总贡献是 (siz_i^{siz_i}n^2(y_r-1)^{-1})
即其生成函数是
用若干联通子图合成总图方案数为
显然答案就是
代码在下
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;
template <typename T>
void read(T &x) {
x = 0; bool f = 0;
char c = getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
for (;isdigit(c);c=getchar()) x=x*10+(c^48);
if (f) x=-x;
}
template<typename F>
inline void write(F x, char ed = '
')
{
static short st[30];short tp=0;
if(x<0) putchar('-'),x=-x;
do st[++tp]=x%10,x/=10; while(x);
while(tp) putchar('0'|st[tp--]);
putchar(ed);
}
template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y); }
template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }
const int P = 998244353;
ll fpw(ll x, ll mi) {
ll res = 1;
for (; mi; mi >>= 1, x = x * x % P)
if (mi & 1) res = res * x % P;
return res;
}
#include <set>
ll n, y, op;
namespace subtask0 {
void main() {
set<pair<int, int> > s;
for (int i = 1, x, y;i < n; i++) {
read(x), read(y); if (x > y) swap(x, y);
s.insert(MP(x, y));
}
int cnt = n;
for (int i = 1, x, y;i < n; i++) {
read(x), read(y); if (x > y) swap(x, y);
if (s.find(MP(x, y)) != s.end()) cnt--;
}
write(fpw(y, cnt));
}
}
namespace subtask1 {
const int N = 200050;
int h[N], ne[N<<1], to[N<<1], tot;
inline void add(int x, int y) {
ne[++tot] = h[x], to[h[x] = tot] = y;
}
ll dp[N][2], Y;
void dfs(int x, int fa) {
dp[x][0] = dp[x][1] = 1;
for (int i = h[x]; i; i = ne[i]) {
int y = to[i]; if (y == fa) continue;
dfs(y, x); ll t0 = dp[x][0], t1 = dp[x][1];
dp[x][0] = t0 * (dp[y][1] + Y * dp[y][0] % P) % P;
dp[x][1] = t1 * (dp[y][1] + Y * dp[y][0] % P) % P + Y * t0 % P * dp[y][1] % P;
dp[x][1] %= P;
}
}
void main() {
for (int i = 1, x, y;i < n; i++)
read(x), read(y), add(x, y), add(y, x);
if (y == 1) return write(fpw(n, n - 2));
ll ans = fpw(y, n) * fpw(n, n - 2) % P;
Y = fpw(y, P - 2) - 1, Y = Y * fpw(n, P - 2) % P;
dfs(1, 0);
write(ans * dp[1][1] % P);
}
}
namespace subtask2 {
const int G = 3;
const int N = 300500;
ll g[N], f[N], A[N], B[N], C[N], D[N], E[N];
int r[N], lim;
void NTT(ll *f, int ty) {
for (int i = 0;i < lim; i++)
if (r[i] > i) swap(f[i], f[r[i]]);
for (int i = 1;i < lim; i <<= 1) {
ll wn = fpw(G, (P - 1) / (i << 1));
for (int j = 0;j < lim; j += (i << 1)) {
ll w = 1;
for (int k = 0;k < i; k++, w = w * wn % P) {
ll x = f[j+k], y = f[i+j+k] * w % P;
f[j+k] = (x + y) % P;
f[i+j+k] = (x - y + P) % P;
}
}
}
if (ty == -1) {
ll inv = fpw(lim, P - 2);
for (int i = 0;i < lim; i++) f[i] = f[i] * inv % P;
reverse(f + 1, f + lim);
}
}
void Inv(int deg, ll *a, ll *b) {
b[0] = fpw(a[0], P - 2); int len;
for (len = 2;len < (deg << 1); len <<= 1) {
lim = len << 1;
for (int i = 0;i < len; i++) A[i] = a[i], B[i] = b[i];
for (int i = 0;i < lim; i++)
r[i] = (r[i>>1]>>1) | ((i & 1) ? len : 0);
NTT(A, 0), NTT(B, 0);
for (int i = 0;i < lim; i++)
b[i] = (2 - A[i] * B[i] % P + P) * B[i] % P;
NTT(b, -1);
for (int i = len;i < lim; i++) b[i] = 0;
}
for (int i = 0;i < len; i++) A[i] = B[i] = 0;
}
ll inv[N];
void init(void) {
inv[0] = inv[1] = 1;
for (int i = 2;i <= n * 2; i++)
inv[i] = inv[P % i] * (P - P / i) % P;
}
void door(ll *a, int deg) {
for (int i = 1;i < deg; i++)
a[i-1] = a[i] * i % P;
a[deg - 1] = 0;
}
void chick(ll *a, int deg) {
for (int i = deg - 2;i >= 0; i--)
a[i + 1] = a[i] * inv[i + 1] % P;
a[0] = 0;
}
void Ln(int deg, ll *a) {
Inv(deg, a, C), door(a, deg);
NTT(a, 1), NTT(C, 1);
for (int i = 0;i < lim; i++)
a[i] = a[i] * C[i] % P;
NTT(a, -1), chick(a, deg);
}
void Exp(int deg, ll *a, ll *b) {
int len; b[0] = 1;
for (len = 2;len < (deg << 1); len <<= 1) {
lim = len << 1;
for (int i = 0;i < len; i++) E[i] = b[i];
Ln(len, E), E[0] = (a[0] + 1 - E[0] + P) % P;
for (int i = 1;i < len; i++)
E[i] = (a[i] - E[i] + P) % P;
NTT(E, 1), NTT(b, 1);
for (int i = 0;i < lim; i++)
b[i] = b[i] * E[i] % P;
NTT(b, -1);
for (int i = len;i < lim; i++) b[i] = 0;
}
}
void main() {
if (y == 1) return write(fpw(n, 2 * n - 4));
ll ans = 1, Y = fpw(y, P - 2) - 1; init();
for (int i = 1;i <= n; i++)
ans = ans * i % P * y % P * Y % P;
ans = ans * fpw(n * n % P * n % P * n % P, P - 2) % P;
ll tmp = n * n % P * fpw(Y, P - 2) % P, jie = 1;
for (int i = 1;i <= n; i++) {
jie = jie * inv[i] % P;
f[i] = tmp * fpw(i, i) % P * jie % P;
// write(f[i], ' ');
}
// puts("");
Exp(n + 1, f, g), write(g[n] * ans % P);
// for (int i = 0;i <= n; i++)
// write(g[i], ' ');
}
}
int main() {
read(n), read(y), read(op);
if (op == 0) subtask0::main();
else if (op == 1) subtask1::main();
else if (op == 2) subtask2::main();
return 0;
}