求组合数有很多种题型,我们需要根据输入的数据的范围来选哪种方式,具体的方式有如下几种:
主要是询问次数和数据大小的不同,对应了不同的解法
此外,另有高精度组合数和卡特兰数两种特例
星号表示本题的思想。
1. 题目
2. 读题(需要重点注意的东西)
思路:
首先,要知道组合数是什么?公式是什么?
一般地,从a个不同的元素中,任取b(b≤a)个元素为一组,叫作从aa个不同元素中取出b个元素的一个组合,这个组合一共有多少组?
普通公式如下:
本题的主要思路是:
卡特兰数
在本题中,我们要求任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。
首先我们将01置于坐标系中,0表示向右走,1表示向上走。
因为0和1的数量都是n,因此一定能走到(n,n)处。
现在关键来了,将错误的路径按红线做轴对称,则为正确的路径。因此对于任意一条非法的路径(橙色),一定对应一条正确的路径(绿色),因为正确的路径的终点是(n,n),则非法的路径的终点一定是(n-1,n+1)
因此,总的可能的走数减去走到(n-1,n+1)的非法路径的总数即为正确的数,即:
3. 解法
---------------------------------------------------解法---------------------------------------------------
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
// 快速幂
int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int main()
{
int n;
cin >> n;
int a = n * 2, b = n;
int res = 1;
for (int i = a; i > a - b; i -- ) res = (LL)res * i % mod;
for (int i = 1; i <= b; i ++ ) res = (LL)res * qmi(i, mod - 2, mod) % mod;
res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;
cout << res << endl;
return 0;
}
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
- 卡特兰数
- 快速幂
6. 总结
求组合数第五种题型(卡特兰数)的模板题,理解卡特兰数的思想并背下代码。
图好像画错了,橙色并不是一条正确的非法路径,非法路径终点也要到(n,n)
很棒欸