BZOJ1856或洛谷1641 [SCOI2010]生成字符串

BZOJ原题链接

洛谷原题链接

可以将\(1\)和\(0\)的个数和看成是\(x\)轴坐标，个数差看成\(y\)轴坐标。
向右上角走，即\(x\)轴坐标\(+1\)，\(y\)轴坐标\(+1\)，表示这一位为\(1\)。
向右下角走，即\(x\)轴坐标\(+1\)，\(y\)轴坐标\(-1\)，表示这一位为\(1\)。

若不考虑题目中的限制，那么这就相当于从\((0, 0)\)出发，走\(n + m\)步到达\((n + m, n - m)\)。
相当于从\(n + m\)步中选出\(n\)步向右上走，所以方案数为\(C_{n + m} ^ n\)。
然后考虑有限制的情况，题目要求在任意的前\(k\)个字符中，\(1\)的个数不能少于\(0\)的个数，在坐标轴上的意义就是不能走到\(y = -1\)这一条线。
于是我们考虑计算出违规情况的方案数，可以将走到\(y = -1\)这条线之前的路线翻折过来。

由于翻折过来会导致向右上走变成向右下走，向右下走变成向右上走，即\(1\)变成\(0\)，\(0\)变成\(1\)，所以违规情况就相当于有\(n + 1\)个\(1\)，\(m - 1\)个\(0\)组成字符串的数量，方案数为\(C_{n + m} ^ {n + 1}\)。
所以最后的答案就是\(C_{n + m} ^ n - C_{n + m} ^ {n + 1}\)，略化简下就是\(\dfrac{(n - m + 1) \times \prod\limits_{i = m + 1} ^ {n + m} i }{(n + 1)!}\)。
求出\((n + 1)!\)的逆元，然后直接全部乘再一起即可，逆元可用费马小定理求。

#include<cstdio>
using namespace std;
const int N = 1e6 + 10;
const int mod = 20100403;
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
int ksm(int x, int y)
{
    int s = 1;
    for (; y; y >>= 1, x = 1LL * x * x % mod)
        if (y & 1)
            s = 1LL * s * x % mod;
    return s;
}
int main()
{
    int i, n, m, s = 1, dv = 1;
    n = re();
    m = re();
    for (i = 2; i <= n + 1; i++)
        dv = 1LL * dv * i % mod;
    for (i = m + 1; i <= m + n; i++)
        s = 1LL * s * i % mod;
    printf("%lld", 1LL * s * (n - m + 1) % mod * ksm(dv, mod - 2) % mod);
    return 0;
}

BZOJ1856或洛谷1641 [SCOI2010]生成字符串

原文：https://www.cnblogs.com/Iowa-Battleship/p/9866617.html