Luogu 5296 生成树计数

标签：ch limits 计数 5296 Luogu sum int define mod

好像有道题是求生成树权值和的和的，考虑 \(\sum\limits_{T}\sum\limits_{e\in E(T)}w_e\) 咋做。

每条边给一个边权 \(v_e(x)=1+w_ex\)，然后跑矩阵树：

\[\text{ans}=[x]\sum\limits_{T}\prod\limits_{e\in E(T)}v_e(x) \]

受到来自神秘力量的启示，我们考虑类似上面这样构造边权。

考虑两个边权 \(a,b\)，构造一个乘法运算，能把 \((a+b)^k\) 弄出来：

\[\begin{aligned}(a+b)^k&=\sum\limits_{i}\dbinom{k}{i}a^ib^{k-i}\\&=\sum\limits_{i}\frac{k!}{i!(k-i)!}a^ib^{k-i}\\\frac{(a+b)^k}{k!}&=\sum\limits_{i}\frac{a^i}{i!}\times \frac{b^{k-i}}{(k-i)!}\\\left[x^k\right]e^{(a+b)x}&=[x^k]e^{ax}\times e^{bx}\end{aligned} \]

其实这就是两个 EGF 的乘法。

所以每条边的边权就是多项式 \(v_e(x)=e^{w_ex}\)，维护前 \(k+1\) 项（\(x^0\to x^k\)）即可。高斯消元求行列式的时候注意求逆需要零次项不为 \(0\)。

#include <bits/stdc++.h>
using namespace std;

namespace vbzIO {
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
	#else
	#define gh() getchar()
	#endif
	#define rd read
	#define wr write
	#define pc putchar
	#define pi pair<int, int>
	#define mp make_pair
	#define fi first
	#define se second
	#define pb push_back
	#define ins insert
	#define era erase
	inline int read () {
		char ch = gh();
		int x = 0;
		bool t = 0;
		while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
		return t ? ~(x - 1) : x;
	}
	inline void write(int x) {
		if (x < 0) {
			x = ~(x - 1);
			putchar('-');
		}
		if (x > 9)
			write(x / 10);
		putchar(x % 10 + '0');
	}
}
using vbzIO::read;
using vbzIO::write;

const int N = 35;
const int mod = 998244353;
int n, k, e[N][N], fac[N], ifac[N], inv[N];

void init(int l) {
	fac[0] = ifac[0] = inv[1] = 1;
	for (int i = 1; i <= l; i++) {
		if (i > 1) inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
		fac[i] = 1ll * fac[i - 1] * i % mod, ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod; 
	}
}

int qpow(int p, int q) {
	int res = 1;
	while (q) {
		if (q & 1) res = 1ll * res * p % mod;
		p = 1ll * p * p % mod, q >>= 1;
	}
	return res;
}

struct ply {
	int w[N];
	ply () { memset(w, 0, sizeof(w)); }
	void mk(int v) {
		for (int i = 0, t = 1; i <= k; i++, t = 1ll * t * v % mod) 
			w[i] = 1ll * ifac[i] * t % mod;
	}
	ply operator + (const ply &rhs) const {
		ply res;
		for (int i = 0; i <= k; i++) 
			res.w[i] = (w[i] + rhs.w[i]) % mod;
		return res;
	}
	ply operator - (const ply &rhs) const {
		ply res;
		for (int i = 0; i <= k; i++) 
			res.w[i] = (w[i] - rhs.w[i] + mod) % mod;
		return res;
	}
	ply operator * (const ply &rhs) const {
		ply res;
		for (int i = 0; i <= k; i++) 
			for (int j = 0; j <= i; j++)
				(res.w[i] += 1ll * w[j] * rhs.w[i - j] % mod) %= mod;
		return res;
	}
	ply inv() {
		ply res; res.w[0] = qpow(w[0], mod - 2);
		for (int i = 1; i <= k; i++) {
			for (int j = 0; j < i; j++) 
				(res.w[i] += (mod - 1ll * res.w[j] * w[i - j] % mod)) %= mod;
			res.w[i] = 1ll * res.w[i] * res.w[0] % mod;
		}
		return res;
	}
} a[N][N], zr;

ply det() {
	ply res; res.mk(0);
	res = res.inv();
	for (int i = 1; i <= n; i++) {
		int p = i;
		while (p <= n && !a[p][i].w[0]) p++;
		swap(a[i], a[p]);
		if (i ^ p) res = zr - res;
		res = res * a[i][i];
		ply iv = a[i][i].inv();
		for (int j = i + 1; j <= n; j++) 
			a[i][j] = a[i][j] * iv;
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			for (int k = i + 1; k <= n; k++) 
				a[j][k] = a[j][k] - a[i][k] * a[j][i];
		}
	}
	return res;
}

int main() {
	n = rd(), k = rd(), init(k);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			e[i][j] = rd();
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			ply tp; tp.mk(e[i][j]);
			a[i][i] = a[i][i] + tp;
			a[j][j] = a[j][j] + tp;
			a[i][j] = a[i][j] - tp;
			a[j][i] = a[j][i] - tp;
		}
	}
	n--;
	ply res = det();
	wr(1ll * res.w[k] * fac[k] % mod);
	return 0;
}

标签：ch,limits,计数,5296,Luogu,sum,int,define,mod
From： https://www.cnblogs.com/Ender32k/p/17569323.html