1 基礎知識

題目：給定n個0和n個1，它們將按照某種順序排成長度為2n的序列，求它們能排成的所有序列中，能夠滿足任意前綴序列中0的個數都不少于1的個數的序列有多少個？
輸出的答案對$10^9+7$取模。

原題目等價于，

在平面直角坐標系xoy下，起點為(0,0)，終點為(n,n)，每次只能向上走一格或向右走一格，問從起點走到終點，且路徑上橫坐標大于等于縱坐標恒成立，求有多少種走法？

用下圖表示即為，

在不觸碰到紅線(即$y=x+1$)的情況下，從起點(0,0)走到終點(n,n)，有多少種走法。

考慮一種觸碰到紅線，走到終點(n,n)的路徑，如下圖粗藍色所顯示路徑。我們將從首次觸碰到紅線的點，記作紅點。那么，將接下來的路徑按照紅線($y=x+1$)對稱，可以得到粗綠色所顯示路徑，最終走到點(n-1,n+1)。

也就是說，任何一條觸碰紅線，走到終點(n,n)的路徑，都可以等效成，一條走到(n-1,n+1)的路徑。而從起點走到點(n-1,n+1)的路徑數為$C_{2n}^{n?1}$，故觸碰紅線走到終點的路徑數目為$C_{2n}^{n?1}$。

題目要計算的是，不觸碰紅線走到終點(n,n)的路徑數目，它等于總路徑數目減去觸碰紅線走到終點(n,n)的路徑數目，即答案可計算如下，
$$C_{2n}^n?C_{2n}^{n?1}=\frac{(2n)!}{n!?n!}?\frac{(2n)!}{(n?1)!?(n+1)!}$$
$$=\frac{(2n)!}{(n?1)!?n!}?(\frac{1}{n}?\frac{1}{n+1})=\frac{(2n)!}{(n?1)!?n!}?\frac{1}{n(n+1)}$$
$$=\frac{(2n)!}{n!?n!}?\frac{1}{n+1}=\frac{C_{2n}^n}{n+1}$$

其中$\frac{C_{2n}^n}{n+1}$即為卡特蘭數。

轉換為代碼，如下，

#include <iostream>using namespace std;const int mod = 1e9 + 7;int qmi(int a, int k, int p) {int res = 1;while (k) {if (k & 1) res = (long long)res * a % p;k >>= 1;a = (long long)a * a % p;}return res;
}int main() {int n;cin >> n;//計算C[2 * n][n] / (n + 1) % modint res = 1;for (int i = 1, j = 2 * n; i <= n; ++i, --j) {res = (long long)res * j % mod;res = (long long)res * qmi(i, mod - 2, mod) % mod;} res = (long long)res * qmi(n + 1, mod - 2, mod) % mod;cout << res << endl;return 0;
}

2 模板

暫無。。。

3 工程化

暫無。。。