题目链接

洛谷

darkbzoj

题意简述

$n$ 个入栈操作，$m$ 个出栈操作，问合法操作序列数。

简要做法

借用一下这篇题解（的图）。

选了 $x$ 个数，$1$ 与 $0$ 个数之差为 $y$，如下图：

不考虑限制条件，方案数为从 $(0,0)$ 到 $(n+m,n-m)$ 的折线数，即从 $n+m$ 次操作中选择 $m$ 次向下： $\binom{n+m}m$。考虑某一种不合法的情况，把这条折线第一次碰到 $y=-1$ 前的部分以 $y=-1$ 为轴翻折，这样就建立了 从 $(0,0)$ 到 $(n+m,n-m)$ 且碰到了 $y=-1$ 的折线 与 从 $(0,-2)$ 到 $(n+m,n-m)$ 的折线 的一一对应，所以不合法的情况个数为 $\binom{n+m}{m-1}$，答案为 $\binom{n+m}m-\binom{n+m}{m-1}$。

（上面看懂了这段可以不看，这段是废话证明）为什么这玩意是双射（一一对应）..其实很简单，每条 从 $(0,0)$ 到 $(n+m,n-m)$ 且碰到了 $y=-1$ 的折线 在第一次碰到 $y=-1$ 前的部分以 $y=-1$ 为轴翻折可以得到唯一一条 从 $(0,-2)$ 到 $(n+m,n-m)$ 的折线，而一条 从 $(0,-2)$ 到 $(n+m,n-m)$ 的折线 必然会碰到 $y=-1$，同样可以把它在第一次碰到 $y=-1$ 前的部分以 $y=-1$ 为轴翻折，就会得到唯一一条 从 $(0,0)$ 到 $(n+m,n-m)$ 且碰到了 $y=-1$ 的折线。

最后吐槽一句。你谷完全不接受做法相同的题解，无法对已有做法进行阐述，所以并没有尝试在你谷发题解。

代码

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int N=1000010;
const int mod=20100403;

int qpow(int x,int y);
int c(int x,int y);

int jc[N<<1];

int main()
{
    int n,m;

    cin>>n>>m;

    jc[0]=1;
    for (int i=1;i<=n+m;++i) jc[i]=(ll)jc[i-1]*i%mod;

    cout<<(c(n+m,m)-c(n+m,m-1)+mod)%mod;

    return 0;
}

int qpow(int x,int y)
{
    int out=1;
    while (y)
    {
        if (y&1) out=(ll)out*x%mod;
        x=(ll)x*x%mod;
        y>>=1;
    }
    return out;
}

int c(int x,int y)
{
    return (ll)jc[x]*qpow(jc[y],mod-2)%mod*qpow(jc[x-y],mod-2)%mod;
}