显然我们需要给出所有弦不交的概率P。

先对分子(两两相连且不相交的情况总数)进行推导:
其实这和经典题目凸多边形的三角形划分很相似(但我也没有做过)。
易知 时有1种情况, 有2种情况。

时有五种情况,如图:

其实这里已经可以大概猜到是卡特兰数了,但是这里我们做一些更严谨的推导,网上的推导要么就是没有,要么就复杂而且不讲人话。下面给出一种简洁的证法来证明连不相交弦的情况总数为卡特兰数。

众所周知,卡特兰数本身和栈/递归联系非常紧密。所以无论是理解还是证明卡特兰数,引入递归的思想十分重要。

图片说明

比如对于n=4的情况,我们轻轻地连一条线。此时圆被我们切割成了两个部分:线的左边和右边。左边和右边都是同样的问题,也就是同质子问题。在这里,线的左边转换成了n=1的情况,线的右边转化成了n=2的情况。不断地分割,直到不可分割(n=0),也是递归的出口。

依次连接1-2,1-4,1-6,1-8,这四种情况就对应着四个分式:

所以数学归纳法推广到

即分子为卡特兰数。故分子满足

下面计算分母

一开始在个点里随便选两个,然后在个点里随便选两个……然后在最后剩下的两个点里面选2个,于是我们就得到了

但是!算重了!

以n=2举例

分别对应

1-2 3-4
1-3 2-4
1-4 2-3
2-3 1-4
2-4 1-3
3-4 1-2

可以发现算重了一遍,但去重并不是/=2

以n=3举例 ,第一轮重复数量/=1,第二轮重复数量/=2,第三轮重复数量/=3.

在上面的计算方式中,每次选取选了两个点确定了一条边,但是这n个边并没有定顺序,所以除以一个全排列

所以我们得到了下面的公式:

化简得到:

然后就很简单了,快速幂+费马小定理得逆元。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll qkpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll getInv(ll a) { return qkpow(a, mod - 2); }  //求一个数的逆元
int main() {
    ll n;
    cin >> n;
    ll ans = 1;
    for (int i = 2; i <= n + 1; ++i) ans *= i, ans %= mod;
    ans = qkpow(2, n) * getInv(ans) % mod;
    cout << ans << endl;
    return 0;
}