题目大意
给一个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 }
Join the discussion