链接：https://ac.nowcoder.com/acm/contest/881/E
来源：牛客网
Bobo has a string of length 2(n + m) which consists of characters `A` and `B`. The string also has a fascinating property: it can be decomposed into (n + m) subsequences of length 2, and among the (n + m) subsequences n of them are `AB` while other m of them are `BA`.
Given n and m, find the number of possible strings modulo (109+7)(109+7).
输入描述:
The input consists of several test cases and is terminated by end-of-file.
Each test case contains two integers n and m.
* 0≤n,m≤1030≤n,m≤103
* There are at most 2019 test cases, and at most 20 of them has max{n,m}>50max{n,m}>50. 输出描述:
For each test case, print an integer which denotes the result.
示例1
输入
1 2 1000 1000 0 0
输出
13 436240410 1
题意：
有一个长度为2（n+m）的字符串，如果它能划分成（n+m）个长度为2的子序列，使得这些子序列有n个是AB，m个是BA，那么这个字符串就合法。给出n和m,问有多少种合法的字符串。
答案
ans= n+m个A和n+m个B任意组合的个数 - 非法字符串的个数
证明思路与卡特兰数公式证明类似
首先有一个贪心思想：
A肯定是先用AB的A，再用BA的A
B肯定是先用BA的B，再用AB的B
所以前n个A配AB，前m个B配BA最优
设A为+1，B为-1，则合法的前缀和-m<=sum[i]<=n ，1<=i<=2*(n+m)
（可以考虑极限情况，即配出了所有AB而BA还没配（-m）和配出了所有BA而AB还没配（n））
https://blog.csdn.net/aiyouyou_/article/details/96450278
现在考虑不合法的情况
因为不合法，那么一定存在一个i,使得sum[i] 等于 -(m+1) 或 （n+1）
分析第一类sum[i]=-(m+1)的情况，显然s[i]=B,且这个B应该是配AB的，但是前面并没有剩余的A能与之相配了
现在我们把前i项A变B，B变A
不妨设原前i项有a个A,b个B，那么后面还有n+m-a个A
前i项变化后，前i项就变成了b个A，那么这个字符串就有n+m-a+b个A
因为b=a+(m+1）
所以也就是有n+m+(m+1)个A，n+m-(m+1）个B
这个过程是可逆的：给定一个由n+m+(m+1)个A，n+m-(m+1）个B组成的序列，则存在A的个数比B的个数多（m+1）个的第一个实例（因为A的个数比B的个数多2*（m+1） >(m+1)）。
颠倒这个实例中的A和B，就得到了第一类不合法的序列，其种数为
第二类不合法情况同理，其种数为
（以上不合法情况种数证明仿照卡特兰数证明）
再考虑一下n=0或m=0的特殊情况即可（其实就是卡特兰数了）
n>0&&m>0 合法字符串的限制条件是-m<=sum[i]<=n
n>0&&m==0 合法字符串的限制条件是0<=sum[i]
n==0&&m>0 合法字符串的限制条件是sum[i]<=0
n==0&&m==0 没有限制条件（答案是1，,只有那个空字符串）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll C[4005][2005];
ll f(int n,int m){
if(C[n][m]) return C[n][m];
if(n==m||m==0) return C[n][m]=1;
if(m>n-m) m=n-m;
return C[n][m]=(f(n-1,m-1)+f(n-1,m))%mod;
}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
ll ans=f((n+m)<<1,n+m);
if(n) ans-=f((n+m)<<1,n-1);
if(m) ans-=f((n+m)<<1,m-1);
ans=(ans%mod+mod)%mod;
printf("%lld\n",ans);
}
return 0;
}
京公网安备 11010502036488号