BZOJ1856 [SCOI2010]生成字符串(组合数学)

题目链接

洛谷

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$ 的折线

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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;
}