AcWing 889. 满足条件的01序列
本博客提供本题截图：
本题解析
我们拿样例去分析，样例3的含义就是给你3个0和3个1，假设有这么一幅图：
我们规定0是往右走，1是向上走一格，按照样例的要求，我们需要向右走三格，向上走三格，那么，不管我们怎么去选择走的方法（0和1的次序），我们的最终都会走到点（3, 3），题中的要求为求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数，即我们需要满足我们路径中任何一个点都不可以超过或碰到如下图所示的红线：
如图，我们的橙色的线条对应的就是一条正确的路线，而蓝色的线条对应的就是一条错误的路线，接着，我们把蓝线第一个接触到红线的点(1,2)开始，其后图像做关于红线对称，可得到绿线如下图所示：
我们不难知道，只要我们有违规的线条（比如上图所示的蓝色的线），在经过上述得到绿线后，最终到达的点都是点(2,4)，即本题结果为：
由特殊到一般，对于每一个n，都有结果为
AC代码
#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; }
三、时间复杂度
关于求组合数各步操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
