UVA11540 Sultan's Chandelier Burnside 引理 + DP

题目传送门

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2535（原题页面）

题解

首先如果两棵树经过一定的旋转以后能够重合，我们就称它们同构。

判断树的同构的常见方法是哈希。但是由于子树的先后顺序是有影响的，只有旋转以后相同才算等价，所以我的哈希方法是直接把所有孩子组成的序列倍长以后，用类似于字符串哈希的方法求出以每个孩子开始一圈的哈希值，取最小的作为当前这棵树的哈希。这样我们就可以轻易的判断两棵子树等不等价了。

然后，我们令 \(dp[x]\) 表示 \(x\) 的子树内，本质不同的染色方案的数量。

根据 Burnside 引理，在求 \(x\) 的方案的时候，我们可以枚举它的孩子们的环的旋转的幅度，然后判断这样旋转合不合法，即——旋转以后对应的两棵子树必须同构。这样，对于一个合法的幅度，这个环一定被分成了一些组，每一组的每棵子树必须使用一样的染色方案。我们把这样的每一组的方案乘起来以后的结果取平均就可以了。

另外，上面是 \(O(n^2)\) 的，实际上可以用 kmp 的最小循环节来线性的求，不详细展开，可以自己研究。

下面是代码，如上文所述，dp 部分的时间复杂度为 \(O(n^2)\)，建树为 \(O(n^2)\)，因此总的时间复杂度为 \(O(Tn^2)\)。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b , 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b , 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I>

inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

const int N = 100 + 7;

const int P = 1e9 + 7;

const int base = 1997;

int n, k, nod;

int siz[N], dp[N], vis[N];

std::vector<int> g[N];

char s[N * 10];

ull h[N], tmp[N << 1], bin[N];

inline int smod(int x) { return x >= P ? x - P : x; }

inline void sadd(int &x, int y) { x += y; x >= P ? x -= P : x; }

inline int fpow(int x, int y) {

	int ans = 1;

	for (; y; y >>= 1, x = (ll)x * x % P) if (y & 1) ans = (ll)ans * x % P;

	return ans;

}

inline int build(int l, int r) {

//	dbg("l = %d, r = %d\n", l, r);

	if (r < l) return ++nod;

	int o = ++nod, pre = l, cnt = 1;

	for (int i = l + 1; i <= r; ++i) {

		if (s[i] == '[') {

			if (!cnt) pre = i;

			++cnt;

		} else if (s[i] == ']') {

			--cnt;

			if (!cnt) g[o].pb(build(pre + 1, i - 1));

		}

	}

	return o;

}

inline void dfs1(int x) {

	siz[x] = 1;

	int cnt = 0;

	for (int y : g[x]) {

		dfs1(y);

		siz[x] += siz[y], ++cnt;

//		tmp[tmp[0] + 1] = tmp[tmp[0]] * base + h[y], ++tmp[0];

	}

	int tt = 0;

	for (int y : g[x]) tmp[tt + 1] = tmp[tt] * base + h[y], ++tt;

	for (int y : g[x]) tmp[tt + 1] = tmp[tt] * base + h[y], ++tt;

//	dbg("****************** %llu %llu %llu %llu %llu\n", tmp[0], tmp[1], tmp[2], tmp[3], tmp[4]);

	for (int i = cnt; i; --i) tmp[i] = tmp[i + cnt] - bin[cnt] * tmp[i];

	std::sort(tmp + 1, tmp + cnt + 1);

//	dbg("****************** %llu %llu %llu %llu %llu,       %llu\n", tmp[0], tmp[1], tmp[2], tmp[3], tmp[4], bin[cnt]);

	if (cnt >= 1) h[x] = tmp[1] * siz[x];

	else h[x] = 1;

//	dbg("******************\n");

//	dbg("h[%d] = %llu, siz = %d\n", x, h[x], siz[x]);

}

inline void dfs2(int x) {

	int cnt = 0, ms = 0;

	dp[x] = 0;

	for (int y : g[x]) dfs2(y), ++cnt;

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

		int flag = 1, s = 1;

		for (int i = 0; i < cnt && flag; ++i) if (!vis[i]) {

			for (int j = i; !vis[j] && flag; j += stp, j >= cnt ? j -= cnt : 0) {

				vis[j] = 1;

				if (h[g[x][i]] != h[g[x][j]]) flag = 0;

			}

		}

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

		if (!flag) continue;

		for (int i = 0; i < cnt; ++i) if (!vis[i]) {

			for (int j = i; !vis[j]; j += stp, j >= cnt ? j -= cnt : 0) vis[j] = 1;

			s = (ll)s * dp[g[x][i]] % P;

		}

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

		sadd(dp[x], s), ++ms;

	}

//	dbg("dp[%d] = %d, ms = %d\n", x, dp[x], ms);

	dp[x] = (ll)dp[x] * fpow(ms, P - 2) % P * k % P;

	if (!cnt) dp[x] = k;

//	dbg("dp[%d] = %d, ms = %d\n", x, dp[x], ms);

}

inline void vec_cls(std::vector<int> &x) {

	std::vector<int> y;

	std::swap(x, y);

}

inline void ycl() {

	bin[0] = 1;

	for (int i = 1; i <= n; ++i) bin[i] = bin[i - 1] * base;

}

inline void work() {

	nod = -1;

	for (int i = 1; i <= n; ++i) vec_cls(g[i]);

	build(1, strlen(s + 1));

	n = nod;

	ycl();

	int ans = 1;

	for (int i = 1; i <= n; ++i) if (!siz[i]) {

		dfs1(i);

		dfs2(i);

		ans = (ll)ans * dp[i] % P;

	}

	static int CS = 0;

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

}

inline void init() {

	memset(siz, 0, sizeof(siz));

	scanf("%s", s + 1);

	read(k);

}

int main() {

#ifdef hzhkk

	freopen("hkk.in", "r", stdin);

#endif

	int T;

	read(T);

	while (T--) {

		init();

		work();

	}

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

UVA11540 Sultan's Chandelier Burnside 引理 + DP

题目传送门

题解

最新文章

热门文章