[考试题] Color

题目大意

给一个N个节点无标号基环外向树, 有M种颜色, 问给这个基环外向树的每个节点染色, 可以染出来的本质不同基环外向树数量对998244353取模。
N≤1e5, M≤1e9

解题报告

我果然把置换群那一套忘完了…今天重温一遍。
首先找出基环, 把环上每棵树dp一遍搞出这棵树染色本质不同的方案数, 顺便把树的结构哈希出来(注意树哈希比较鬼畜…为了防重最好把深度和子树大小什么的一起哈希进去), 这样问题就转化为一个环, 每个点可以染dp[i]种颜色中的一种, 每个节点的特征码为hash[i], 问这个环在任意旋转置换下的本质不同染色方案数。
然后这就是经典的burnside+polya计数了, 考虑在旋转i次置换的循环节大小为N/gcd(i, N), 那么一共有gcd(i, N)个循环节, 循环之间互不干扰, 于是乘起来即可算出等价类数目, 最后除以置换群大小得到结果。

后记

最近一直使用linux, 学了一发gdb命令行调试, 简直爽歪歪, 对codeblocks强大调试功能产生依赖后感到非常无奈…

以及找到了onenote在Linux下的替代品(雾):git.coding.net+git定时push

我真机智qwq

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <vector>
#include <algorithm>
#define PAUSE {char Hinevenqwq; while((Hinevenqwq = getchar()) != EOF && Hinevenqwq != 'c') ;}
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
inline int getInt () {
	int ret; char ch; bool flg = false;
	while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
	ret = ch-'0';
	while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0');
	return flg ? -ret : ret;
}
const int MAXN = 100010*2;
const int MOD = 1000000007;
int dir[MAXN];
bool tmp[MAXN];
bool vis_cir[MAXN];
vector<int> circ;
bool dfsCirc (int u) {
	if(tmp[u]) {vis_cir[u] = true; circ.push_back(u); return true ;}
	tmp[u] = true;
	bool f = dfsCirc(dir[u]);
	if(f) {
		if(!vis_cir[u]) {
			vis_cir[u] = true;
			circ.push_back(u);
			return true;
		} else return false;
	}
	return false;
}
inline int advPow (int a, int b) {
	int ret = 1;
	while(b) {
		if(b&1) ret = (LL)ret*a%MOD;
		a = (LL)a*a%MOD;
		b >>= 1;
	}
	return ret;
}
int fac[MAXN*2], finv[MAXN*2];
inline int C (int N, int M) {
	if(N < M) return 0;
	return (LL)fac[N]*finv[M]%MOD*finv[N-M]%MOD;
}
struct Node {
	int v, nxt;
} d[MAXN];
int head[MAXN], etot;
inline void addEdge (int a, int b) {
	etot ++;
	d[etot].v = b;
	d[etot].nxt = head[a];
	head[a] = etot;
}
int N, M;
int dp[MAXN];
ULL hashc[MAXN];
inline bool compV (int a, int b) {return hashc[a] < hashc[b];}
const ULL SEED = 131;
int calc (int N, int M) {
	int t = min(N, M);
	int curv = 1, ret = 0;
	for(int i = 1; i<=t; i++) {
		curv = (LL)curv*(M-i+1)%MOD;
		ret = (ret+(LL)curv*finv[i]%MOD*C(N-1, i-1)%MOD)%MOD;
	}
	return ret;
}
int sz[MAXN];
ULL dfs (int u, int f, int dep) {
	vector<ULL> buf;
	sz[u] = 1;
	for(int e = head[u]; e; e = d[e].nxt) {
		if(vis_cir[d[e].v] || d[e].v == f) continue ;
		dfs(d[e].v, u, dep+1);
		sz[u] += sz[d[e].v];
		buf.push_back(d[e].v);
	}
	sort(buf.begin(), buf.end(), compV);
	for(int i = 0; i<(int)buf.size(); i++)
		hashc[u] = hashc[u]*SEED+hashc[buf[i]];
	hashc[u] = hashc[u]*137^dep^(sz[u]<<1);
	dp[u] = M%MOD;
	for(int i = 0; i<(int)buf.size(); ) {
		int j = i;
		while(j < (int)buf.size() && hashc[buf[j]] == hashc[buf[i]]) j ++;
		int len = j-i;
		dp[u] = (LL)dp[u]*calc(len, dp[buf[i]])%MOD;
		i = j;
	}
	//printf("dp[%d]:%d\n", u, dp[u]);
	return hashc[u];
}
ULL hlinr[MAXN*2], pwr[MAXN];
int pref_prd[MAXN];
int gcd (int a, int b) {
	return b ? gcd(b, a%b) : a;
}
int main () {
	freopen("color.in", "r", stdin);
	freopen("color.out", "w", stdout);
	scanf("%d%d", &N, &M);
	for(int i = 1; i<=N; i++) {
		dir[i] = getInt();
		addEdge(dir[i], i);
	}
	fac[0] = 1;
	for(int i = 1; i<=(N<<1); i++) fac[i] = (LL)fac[i-1]*i%MOD;
	finv[N<<1] = advPow(fac[N<<1], MOD-2);
	for(int i = (N<<1)-1; i>=0; i--) finv[i] = (LL)finv[i+1]*(i+1)%MOD;
	dfsCirc(1);
	for(int i = 0; i<(int)circ.size(); i++)
		dfs(circ[i], 0, 1);
	int W = circ.size();
	for(int i = 1; i<=(int)circ.size(); i++)
		hlinr[i] = hlinr[W+i] = hashc[circ[i-1]];
	for(int i = 1; i<=(W<<1); i++)
		hlinr[i] += hlinr[i-1]*SEED;
	pwr[0] = 1;
	for(int i = 1; i<=W; i++) pwr[i] = pwr[i-1]*SEED;
	pref_prd[0] = 1;
	for(int i = 1; i<=W; i++) pref_prd[i] = (LL)pref_prd[i-1]*dp[circ[i-1]]%MOD;
	int ans = 0, rv = 0;
	for(int i = 1; i<=W; i++) {
		if(hlinr[W+i]-hlinr[i]*pwr[W] != hlinr[W]) continue ;
		ans = (ans+pref_prd[gcd(i, W)])%MOD, rv++;
	}
	printf("%lld\n", (LL)ans*advPow(rv, MOD-2)%MOD);
	PAUSE
}