@hdu - 5822@ color

@description@
@solution@
@accepted code@
@details@

@description@

给定一个每个点出度都为 1 的有向连通图以及 m 种颜色。求本质不同的染色方案数。

@solution@

其实就是基环树。

考虑一棵有根树的本质不同染色方案：先递归处理出子树答案，通过树哈希把它长得一样的子树放在一起。

对于长得相同的子树，假如有 x 个，这子树的染色方案为 f[x]，则它们的贡献为 C(f[x] + x - 1, x)。一个不难理解的组合问题。

注意那个组合数直接暴力算就好了，因为 ∑x = n。

再考虑环，可以使用 burnside 引理解决，是个经典的模型。

不过注意环旋转过后对应位置的树哈希值必须相等，否则这个置换是不合法的，不能算入最后的置换群大小中。

为了保证这一点，可以先求出所有可行循环节大小。转成 border 用 kmp 求即可。

总时间复杂度 O(nlogn)。

@accepted code@

#include <map>

#include <vector>

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef unsigned long long ull;

const int MAXN = 100000;

const int MOD = int(1E9) + 7;

const int HASHMOD = 19260817;

int pow_mod(int b, int p) {

	int ret = 1;

	for(int i=p;i;i>>=1,b=1LL*b*b%MOD)

		if( i & 1 ) ret = 1LL*ret*b%MOD;

	return ret;

}

struct dhash{

	ull h1; int h2; dhash() : h1(0), h2(0) {}

	dhash(ull _h1, int _h2) : h1(_h1), h2(_h2) {}

	friend dhash operator + (const dhash &a, const dhash &b) {

		return dhash(a.h1 + b.h1, (a.h2 + b.h2 >= HASHMOD ? a.h2 + b.h2 - HASHMOD : a.h2 + b.h2));

	}

	friend dhash operator - (const dhash &a, const dhash &b) {

		return dhash(a.h1 - b.h1, (a.h2 - b.h2 < 0 ? a.h2 - b.h2 + HASHMOD : a.h2 - b.h2));

	}

	friend dhash operator * (const dhash &a, const dhash &b) {

		return dhash(a.h1 * b.h1, 1LL * a.h2 * b.h2 % HASHMOD);

	}

	friend bool operator < (const dhash &a, const dhash &b) {

		return (a.h1 == b.h1 ? a.h2 < b.h2 : a.h1 < b.h1);

	}

	friend bool operator == (const dhash &a, const dhash &b) {

		return ((!(a < b)) && (!(b < a)));

	}

	friend bool operator != (const dhash &a, const dhash &b) {

		return a < b || b < a;

	}

};

int f[MAXN + 5], n, m;

bool tag[MAXN + 5], vis[MAXN + 5];

int get(int x) {

	vis[x] = true;

	if( vis[f[x]] ) {

		tag[x] = true;

		return f[x];

	}

	int ret = get(f[x]);

	if( ret != -1 )

		tag[x] = true;

	return (ret == x ? -1 : ret);

}

dhash h[MAXN + 5], sed[MAXN + 5], pw[2*MAXN + 5];

int dp[MAXN + 5], iv[MAXN + 5], siz[MAXN + 5];

vector<int>v[MAXN + 5];

int comb(int n, int m) {

	n = ((n + m) % MOD + MOD - 1) % MOD;

	int ret = 1;

	for(int i=1;i<=m;i++)

		ret = 1LL*ret*(n-i+1)%MOD*iv[i]%MOD;

	return ret;

}

pair<dhash, int>tmp[MAXN + 5];

void dfs(int x) {

	siz[x] = 1, h[x] = dhash(1, 1);

	for(int i=0;i<(int)v[x].size();i++) {

		int to = v[x][i];

		if( tag[to] ) continue;

		dfs(to); siz[x] += siz[to];

		h[x] = h[x] + sed[siz[to]] * h[to];

	}

	int tot = 0;

	for(int i=0;i<(int)v[x].size();i++) {

		int to = v[x][i];

		if( tag[to] ) continue;

		tmp[++tot] = make_pair(h[to], dp[to]);

	}

	sort(tmp + 1, tmp + tot + 1), dp[x] = m;

	for(int i=1;i<=tot;i++) {

		int j = i;

		while( j < tot && tmp[i].first == tmp[j + 1].first )

			j++;

		dp[x] = 1LL*dp[x]*comb(tmp[i].second, j - i + 1)%MOD;

		i = j;

	}

}

int b[MAXN + 5], c[MAXN + 5], cnt;

int con[MAXN + 5], tot;

int gcd(int x, int y) {

	return (y == 0 ? x : gcd(y, x % y));

}

int fail[MAXN + 5], prod[MAXN + 5];

int solve1() {

	prod[0] = c[0];

	for(int i=1;i<cnt;i++)

		prod[i] = 1LL*prod[i - 1]*c[i]%MOD;

	fail[0] = -1, fail[1] = 0;

	for(int i=2;i<=cnt;i++) {

		int j = fail[i - 1];

		while( j != -1 && b[j] != b[i-1] )

			j = fail[j];

		fail[i] = j + 1;

	}

	for(int i=1;i<=cnt;i++) con[i] = 0;

	for(int p=cnt;fail[p]!=-1;p=fail[p])

		con[cnt - fail[p]] = prod[cnt - fail[p] - 1];

/*

	for(int i=1;i<=cnt;i++) {

		if( cnt % i == 0 ) {

			bool flag = true;

			for(int j=i;j<cnt;j++)

				if( b[j-i] != b[j] ) {

					flag = false;

					break;

				}

			if( flag ) {

				con[i] = 1;

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

					con[i] = 1LL*con[i]*c[j]%MOD;

			}

			else con[i] = 0;

		}

	}

*/

	int ans = 0; tot = 0;

	for(int i=0;i<cnt;i++) {

		int x = gcd(i, cnt);

		if( con[x] ) ans = (ans + con[x]) % MOD, tot++;

	}

	return ans;

}

int solve() {

	int ret = solve1();

	return 1LL*ret*pow_mod(tot, MOD-2)%MOD;

}

int a[MAXN + 5], dcnt; dhash d[MAXN + 5];

int read() {

	int x = 0, ch = getchar();

	while( ch > '9' || ch < '0' ) ch = getchar();

	while( '0' <= ch && ch <= '9' ) x = 10*x + ch - '0', ch = getchar();

	return x;

}

void work() {

	n = read(), m = read();

	for(int i=1;i<=n;i++) v[i].clear(), tag[i] = vis[i] = false;

	for(int i=1;i<=n;i++) v[f[i] = read()].push_back(i);

	get(1);

	for(int i=1;i<=n;i++)

		if( tag[i] ) dfs(i);

	cnt = 0;

	for(int i=1;i<=n;i++)

		if( tag[i] ) {

			int p = i;

			do {

				a[cnt++] = p;

				p = f[p];

			}while( p != i );

			break;

		}

	dcnt = 0;

	for(int i=0;i<cnt;i++) d[++dcnt] = h[a[i]];

	sort(d + 1, d + dcnt + 1), dcnt = unique(d + 1, d + dcnt + 1) - d - 1;

	for(int i=0;i<cnt;i++) b[i] = lower_bound(d + 1, d + dcnt + 1, h[a[i]]) - d, c[i] = dp[a[i]];

	printf("%d\n", solve());

}

ull get_rand() {

	ull p = rand() << 16 | rand();

	ull q = rand() << 16 | rand();

	return p << 32 | q;

}

void init() {

	for(int i=0;i<=MAXN;i++) {

		ull p = get_rand();

		sed[i] = dhash(p, int(p % HASHMOD));

	}

	iv[1] = 1;

	for(int i=2;i<=MAXN;i++)

		iv[i] = MOD - 1LL*(MOD/i)*iv[MOD%i]%MOD;

	pw[0] = dhash(1, 1), pw[1] = dhash(1313131, 1313131);

	for(int i=2;i<=2*MAXN;i++)

		pw[i] = pw[i-1] * pw[1];

}

int main() {

	srand(20041112), init();

	int T; scanf("%d", &T);

	while( T-- ) work();

}

@details@

貌似有点小卡常，不知道是不是我常数太大。

巴特西

@hdu - 5822@ color

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章