显然我们需要给出所有弦不交的概率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; }