洛谷P1641 [SCOI2010]生成字符串 解题报告

题面

lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？

输入输出格式

输入格式：

输入数据是一行，包括2个数字n和m

输出格式：

输出数据是一行，包括1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以20100403的余数

输入输出样例

说明

对于30%的数据，保证1<=m<=n<=1000

对于100%的数据，保证1<=m<=n<=1000000

本题解主要为让本蒟蒻理清思路，因此在叙述上可能会有些繁琐orz

首先我们分析一下题目要求，用n个1和m和0组成字符串，且截至到任意位置，1的个数一定大于等于0的个数。

我们考虑建立一个平面直角坐标系，x坐标轴表示1和0的个数和，y坐标轴表示1和0的个数差。

因此只要选一个新的数字，就是向右走。若选择0就是向右下（1的个数减去0的个数变少了一个），同理选择1就是向右上走（1的个数减去0的个数增加）。

由于直接求合法方案数比较困难，所以先求出全部方案数再减去不合法方案数。

• 全部方案数：从(0,0)点走到(n+m,n-m)点的个数。即选择了全部n+m个数字，1的个数比0的个数恰好多了n-m个。

　　　即从n+m个数中选择了n个1——C(n+m,n)或C(n+m,m)。

• 再考虑不合法方案数，任意一点的 1个数减0个数 小于零，即经过 y=-1 这条线的情况全部不合法。

　　　利用等效替代法：

　　　　　我们把不合法的情况在经过 y=-1 这条线之前的线以 y=-1 为对称轴向下翻折。起点就变成了 (0,-2)，终点仍然是 (n+m,n-m)。

　　　　　再沿y轴向上平移2个单位，即从(0,0)走到(n+m,n-m+2)，即选择n+1个1，m-1个0。

　　　故不合法方案数等于C(n+m,n+1)。

答案即  C(n+m,n) - C(n+m,n+1)。

代码如下

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 
 5 const int p=20100403;
 6 int n,m;
 7 const int N=1e6+5;
 8 ll jc[N<<1];
 9 
10 inline ll ksm(ll a,ll b)
11 {
12     ll ans=1;
13     while(b)
14     {
15         if(b&1) ans=(ans*a)%p;
16         a=(a*a)%p;
17         b>>=1;
18     }
19     return ans;
20 }
21 
22 inline ll C(int a,int b)
23 {
24     return jc[a]*ksm(jc[a-b]*jc[b]%p,p-2)%p;
25 }
26 
27 int main()
28 {
29     scanf("%d%d",&n,&m);
30     jc[1]=1;
31     for(int i=2;i<=m+n;i++)
32     {
33         jc[i]=jc[i-1]*i%p;
34     }
35     cout<<(C(n+m,m)-C(n+m,m-1)+p)%p;
36 }

View Code

洛谷P1641 [SCOI2010]生成字符串 解题报告

原文：https://www.cnblogs.com/chu-xuan/p/10086499.html