牛客多校第一场——E-ABBA

题目：

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)(10^9+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 \leq n, m \leq 10^30≤n,m≤103
• There are at most 2019 test cases, and at most 20 of them has max⁡{n,m}>50\max{n, m} > 50max{n,m}>50.

输出描述

For each test case, print an integer which denotes the result.

样例

输入；
1 2
1000 1000
0 0
输出：
13
436240410
1

大致题意：

有一个人有一种字符串（长度为2*（n+m)），这个字符串中含有n个AB和m个BA，AB和BA不连续也是可以的，只要求相对位置满足要求就行，现在问你和那个人一样的满足这种要求的字符串到底有多少个。

思路

一种贪心的思路，然后dp实现。
dp[i][j]表示用了i个A和j个B的方案数。
贪心和dp：
要是A的话，肯定是要先要满足n个AB,然后假如现在已经有了j个B，那么最多只能有j+n个A,
所以当i-n<j的时候
dp[i+1][j]+=dp[i][j];
同理
B的情况也是一样，肯定要先满足m个BA，然后假如现在有i个A，那么最多现在只能有i+m个B；
所以当j-n<m的时候
dp[i][j+1]+=dp[i][j];

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
long long  dp[2005][2005];
int n,m;
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        int sum=n+m;
        dp[0][0]=1;
        for(int i=0;i<=sum;i++)
        {
            for(int j=0;j<=sum;j++)
            {
                if(i-n<j)
                {
                    dp[i+1][j]+=dp[i][j];
                    dp[i+1][j]%=1000000007;
                }
                if(j-m<i)
                {
                    dp[i][j+1]+=dp[i][j];
                    dp[i][j+1]%=1000000007;
                }
            }
        }
        printf("%lld\n",dp[sum][sum]);
        for(int i=0;i<=sum+1;i++)
        {
            for(int j=0;j<=sum+1;j++)
            {
                dp[i][j]=0;
            }
        }
    }
    return 0;
}