http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1639
假如一开始有一根绳子。
那么增加一根的时候，可以插在它的尾部，也可以左端头开始插，或者右端头开始插。但是不能从头部开始插，因为这样和前面的重复了。因为它是环，旋转一下，变成一模一样了。
那么加入有2根了，就可以在第一、二根中间开始插，或者在第二根尾部开始插，也是可以左端头开始插，或者右端头开始插。
所以总方案就是2^(n - 1) * (n - 1)!
那么总方案数有多少呢？
考虑下一共结成了n个结，然后每一个结都是任取两个端点形成的。那么就是C(2n, 2) * C(2n - 2, 2) .... C(2, 2)
那么顺序不管，就是要除以n!
所以最后的公式是：
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) #define inf (0x3f3f3f3f) typedef long long int LL; using namespace std; void work() { int n; cin >> n; double ans = 1.0; for (int i = 1; i <= n - 1; ++i) { ans *= 2; ans *= i; ans *= (i + 1); int t = (i + 1) * 2; ans /= t * (t - 1) / 2; } cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
原文：http://www.cnblogs.com/liuweimingcprogram/p/6288102.html
