HDU 5552 Bus Routes（2015合肥现场赛A，计数，分治NTT)

题意给定n个点，任意两点之间可以不连边也可以连边。如果连边的话可以染上m种颜色。

求最后形成的图，是一个带环连通图的方案数。

首先答案是n个点的图减去n个点能形成的树。

n个点能形成的树的方案数比较好求，根据prufer序列可以知道n个点形成的无根树的个数为$n^{n-2}$

那么现在问题变成求n个点形成的连通图的个数。

图有连通和不连通的，那么就是图的总数减去不连通的图的总数。

图的总数很简单，$m^{\frac{n(n-1)}{2}}$，那么现在要求不连通的图的总数。

设$f(n)$为$n$个点的不连通的图的总数

$f(n) = ∑f(i) * C(n - 1, i - 1) * f(n - i)$，$i$从$1$到$n-1$。

这是一个卷积的形式，可以分治NTT来求，就可以了。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define	dec(i, a, b)	for (int i(a); i >= (b); --i)

#define	fi		first

#define	se		second

#define	MP		make_pair

typedef long long LL;

const LL G = 106;

const LL mod = 152076289;

const LL N = 4e4 + 10;

int T;

int ca = 0;

LL x1[N], x2[N];

LL ans;

LL n, m;

LL f[N], g[N], h[N];

LL c[N], fac[N], ifac[N];

LL Pow(LL a, LL b){

	LL ret = 1;

	while (b){

		if (b & 1) ret = (ret * a) % mod;

		a = (a * a) % mod;

		b >>= 1;

	}

	return ret;

}  

void change (LL *y, int len){

	int i, j, k;

	for (i = 1, j = len / 2; i < len - 1; i++) {

		if (i < j) swap(y[i], y[j]);

		k = len / 2;

		while (j >= k) {

			j -= k;

			k /= 2;

		}

		if (j < k) j += k;

	}

}

void ntt (LL *y, int len, int on) {

	change (y, len);

	int id = 0;

	for(int h = 2; h <= len; h <<= 1) {

		id++;

		LL wn = Pow (G, (mod - 1) / (1<<id));

		for(int j = 0; j < len; j += h) {

			LL w = 1;

			for(int k = j; k < j + h / 2; k++) {

				LL u = y[k] % mod;

				LL T = w * (y[k + h / 2] % mod) % mod;

				y[k] = (u + T) % mod;

				y[k + h / 2] = ((u - T) % mod + mod) % mod;

				w = w * wn % mod;

			}

		}

	}

	if (on == -1){

		for (int i = 1; i < len / 2; i++)

			swap (y[i], y[len - i]);

		LL inv = Pow(len, mod - 2);

		for(int i = 0; i < len; i++)

			y[i] = y[i] % mod * inv % mod;

	}

}

void solve(int l, int r){

	if (l == r){

		f[l] += g[l];

		f[l] %= mod;

		return;

	}

	int mid = (l + r) >> 1;

	solve(l, mid);

	int len = 1;

	while (len <= r - l + 1) len <<= 1;

	rep(i, 0, len - 1) x1[i] = x2[i] = 0;

	rep(i, l, mid)   x1[i - l] = f[i] * ifac[i - 1] % mod;

	rep(i, 1, r - l) x2[i - 1] = g[i] * ifac[i] % mod;

	ntt(x1, len, 1);

	ntt(x2, len, 1);

	rep(i, 0, len - 1) x1[i] = x1[i] * x2[i] % mod;

	ntt(x1, len, -1);

	rep(i, mid + 1, r){

		f[i] -= x1[i - l - 1] % mod * fac[i - 1] %mod;

		(f[i] += mod) %= mod;

	}

	solve(mid + 1, r);

}

int main(){

	fac[0] = 1;

	rep(i, 1, N - 1) fac[i] = fac[i - 1] * i % mod;

	ifac[N - 1] = Pow(fac[N - 1], mod - 2);

	dec(i, N - 2, 0) ifac[i] = ifac[i + 1] * (i + 1) % mod;

	scanf("%d", &T);

	while (T--){

		scanf("%lld%lld", &n, &m);

		memset(f, 0, sizeof f);

		rep(i, 1, n) g[i] = Pow(m + 1, 1ll * i * (i - 1) / 2);

		solve(1, n);

		ans = (f[n] - Pow(n, n - 2) * Pow(m, n - 1) % mod + mod) % mod;

		printf ("Case #%d: %lld\n", ++ca, ans);

	}

	return 0;

}

巴特西

HDU 5552 Bus Routes（2015合肥现场赛A，计数，分治NTT)

最新文章

热门文章