2019牛客多校第一场 E ABBA 组合数学 && DP

看了一天的题目，终于把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个'AB' 与 m个'BA'组成，长度为2*(n+m)。

题目思路:首先了解一个性质，就是前n个A一定属于AB里面的A，有些人可能不太懂这里，我用一个样例来说明一下: 【BAAB】

上面的例子在n=1，m=1的时候是成立的。但有人会一眼就看出来，这不是第一个A属于BA吗，在这么看来是的，但是他也属于AB : BAAB,这样他就属于 AB 了，第二个A也就属于BA。所以说无论如何来说，我们总能找到前n个A属于AB ，因为如果有一个属于BA的话，这个A之前的B可以与后面的A组成BA。所以我们可以假设为前n个A一定属于AB，前m个B一定属于BA。由这个结论我们可以得出两种解法一种DP 另一种组合数学，下面开始：

一、动态规划(DP)

第一：考虑为什么可以满足动态规划，我们用 f(i,j) 来表示，有i个A，j个B时有多少个合法的，所以我们需要考虑合法条件，考虑完合法条件之后，在满足合法的情况下，我们用二维dp去推，每一个 (i,j)的点都与 (i-1)和(j-1)有关，所以说 (i,j)的两点的状态就是这两点状态的和，然后我们每次保证过程合法，一直推到n+m,m+n即可。

第二：考虑合法条件：我们根据前提贪心性质，我们让前n个A属于AB，多出来的A再分给BA，对于B同理:

所以我们得到如下：

{

i+1<=n f(i+1,j)+=f(i,j) //当i+1小于n个A时，由于这都是属于AB的A，所以下一个A可以放

i+1<=j+n f(i+1,j)+=f(i,j) //如果i+1大于n，那么j>=(i+1-n)__也就是说B的数量要比剩余A的数量多才能组成合法的。

j+1<=m f(i,j+1)+=f(i,j) //同理

j+1<=i+m f(i,j+1)+=f(i,j) //同理

}

所以说我们由这个可以一直递推下去，最后输出f(n+m,n+m)，注意取余与初始状态(0,0的时候，n=0,m=0空字符串满足1)

所以AC代码：

int dp[3005][3005];
int main()
{
    while(~scanf("%lld%lld",&n,&m))
    {
        for(int i=0;i<=n+m;i++)
            for(int k=0;k<=n+m;k++) dp[i][k]=0;
        dp[0][0]=1;
        for(int i=0;i<=n+m;i++)
        {
            for(int j=0;j<=n+m;j++)
            {
                if(i+1<=j+n) dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
                if(j+1<=i+m) dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
            }
        }
        printf("%lld\n",dp[n+m][n+m]);
    }
    return 0;
}