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/