Brief description:
外面有一圈 n 个结点，中心有一个结点与 n 个结点都相连，问这个共 2n 条边的轮状图的生成树的方案数。
旋转相同视为等价。
Analysis:
Burnside 引理：
相当于染色有限制。。因此只能退到 Burnside 引理。。。。。
回忆 POJ 2154. color 中的方法。。
（置换 $$\rho_i$$ 的循环数为 gcd(i, n)）
（gcd(i, n) == d 的置换。。有 phi(n/d) 种。。）
为了使得经过置换后的染色不变。。必须每个循环中的染色方式相同。。。。
也就是相当于求 T(d)。。。这里的 T() 表示，不考虑旋转时的方案数。。
这样我们就成功的把问题转换为了求不考虑旋转时的方案数。
不考虑旋转：
任意取两个结点讨论 a, b。那么总数便是 a, b 断开的种数与 a, b 连在一起的种数的和。
f(n) 表示外圈有 n 个结点时，而 a, b 是断开的种数。
g(n) 表示外圈有 n 个结点时，而 a, b 是连在一起的种数。
那么有 T(n) = f(n) + g(n)
$$!f_n = \sum_{i=0}^{n-1} (n-i) f_i $$
$$!f_0 = 1$$
$$!g_n = \sum_{i=0}^{n-1} i(i-1) f_{n-i}$$
$$!g_1 = 0$$
这里 f_n 数列恰好是 http://oeis.org/A088305
经过一番化简化简。。
得到
$$!f_n = 3 f_{n-1} – f_{n-2} $$
$$!g_n = 2(f_n-f_{n-1}-1) $$
注意边界即可。。
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2950118
...
LL f(int n){
if (!n) return 1;
return pow(A0, n).d[0][1];
}
LL g(int n){
if (n==1) return 0;
return pdtll(2, dffll(dffll(f(n), f(n-1)), 1));
}
LL T(int n){
if (n==1) return 1;
return (f(n)+g(n)) % MOD;
}
...
void dfs(int k = 0, int d = 1){
if (k == SZ(fac)){
INCll(z, pdtll(get_phi(n/d), T(d)));
}
else{
REP(i, fac[k].se+1){
dfs(k+1, d);
d *= fac[k].fi;
}
}
}
References:
http://blog.csdn.net/acm_cxlove/article/details/7868589
http://hi.baidu.com/spellbreaker/item/d8bb3bda5af30be6795daa93
http://endlesscount.blog.163.com/blog/static/8211978720122149120772/
