某岛

… : "…アッカリ~ン . .. . " .. .
November 7, 2014

HDU 2481. Toy

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/