ABBA（组合数学/dp）

链接：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;
}