静态网站开发试验报告,十大搜索引擎地址,如何做网站短链接,扬州网络推广公司目录 1 基础知识2 模板3 工程化 1 基础知识
题目#xff1a;给定n个0和n个1#xff0c;它们将按照某种顺序排成长度为2n的序列#xff0c;求它们能排成的所有序列中#xff0c;能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个#xff1f; 输出的答案对 1 0 … 目录 1 基础知识2 模板3 工程化 1 基础知识
题目给定n个0和n个1它们将按照某种顺序排成长度为2n的序列求它们能排成的所有序列中能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个 输出的答案对 1 0 9 7 10^97 1097取模。
原题目等价于
在平面直角坐标系xoy下起点为(0,0)终点为(n,n)每次只能向上走一格或向右走一格问从起点走到终点且路径上横坐标大于等于纵坐标恒成立求有多少种走法
用下图表示即为
在不触碰到红线(即 y x 1 yx1 yx1)的情况下从起点(0,0)走到终点(n,n)有多少种走法。 考虑一种触碰到红线走到终点(n,n)的路径如下图粗蓝色所显示路径。我们将从首次触碰到红线的点记作红点。那么将接下来的路径按照红线( y x 1 yx1 yx1)对称可以得到粗绿色所显示路径最终走到点(n-1,n1)。 也就是说任何一条触碰红线走到终点(n,n)的路径都可以等效成一条走到(n-1,n1)的路径。而从起点走到点(n-1,n1)的路径数为 C 2 n n − 1 C_{2n}^{n-1} C2nn−1故触碰红线走到终点的路径数目为 C 2 n n − 1 C_{2n}^{n-1} C2nn−1。
题目要计算的是不触碰红线走到终点(n,n)的路径数目它等于总路径数目减去触碰红线走到终点(n,n)的路径数目即答案可计算如下 C 2 n n − C 2 n n − 1 ( 2 n ) ! n ! ⋅ n ! − ( 2 n ) ! ( n − 1 ) ! ⋅ ( n 1 ) ! C_{2n}^n-C_{2n}^{n-1}\frac{(2n)!}{n!\cdot n!} - \frac{(2n)!}{(n-1)!\cdot (n1)!} C2nn−C2nn−1n!⋅n!(2n)!−(n−1)!⋅(n1)!(2n)! ( 2 n ) ! ( n − 1 ) ! ⋅ n ! ⋅ ( 1 n − 1 n 1 ) ( 2 n ) ! ( n − 1 ) ! ⋅ n ! ⋅ 1 n ( n 1 ) \frac{(2n)!}{(n-1)!\cdot n!}\cdot (\frac{1}{n} - \frac{1}{n1})\frac{(2n)!}{(n-1)!\cdot n!}\cdot \frac{1}{n(n1)} (n−1)!⋅n!(2n)!⋅(n1−n11)(n−1)!⋅n!(2n)!⋅n(n1)1 ( 2 n ) ! n ! ⋅ n ! ⋅ 1 n 1 C 2 n n n 1 \frac{(2n)!}{n!\cdot n!} \cdot \frac{1}{n1}\frac{C_{2n}^n}{n1} n!⋅n!(2n)!⋅n11n1C2nn
其中 C 2 n n n 1 \frac{C_{2n}^{n}}{n1} n1C2nn即为卡特兰数。
转换为代码如下
#include iostreamusing 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 工程化
暂无。。。
