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;
}

二、组合数学

首先我们算出所有情况，假设有(n+m)*2个位置，我们n+m个位置放A，剩余位置放B，则总的排列方案 C(2n+2m,n+m)【这也是所有方案了，包括不合法】

之后我们把不合法的方案去除：

证明方法如下【我们先排除A不合法】:

取A为1，B为-1，则合法序列的任意点出前缀和的范围为 -m<=sum[i]<=n （考虑极限情况，AB已经排满BA一个没排与BA已经排满AB一个没排）

那么如果不合法的话，这个序列就在某个点的前缀和为 -(m+1) 【按A来考虑】，而且这个多出的B本应该和AB合，但是前面没有。

现在我们把这个节点前的 a与b互换，也就是说设I之前就 x个A与y个B，那么i之后就有 n+m-x个A与n+m-y个B

互换之后，现在这个字符串就有n+m-x+y个A与n+m-y+x个B

由于x-y=-(m+1) x=y-(m+1) 所以整个字符串中有 n+m-y+(m+1)+y 个A，有n+m-y+y-(m+1)个B

由于过程可逆，所以存在这种由n+m+m+1个A n+1个B序列使得序列不合法【这里为什么可逆我也不明白，待我再看一下组合数学】

所以第一种不合法的序列：C(2n+2m,n+1)

同理可得第二种不合法序列：C(2n+2m,m-1)

所以答案就是：ans=C(2n+2m,n+m)-C(2n+2m,n+1)-C(2n+2m,m-1)

根据这个答案就可以推出来了，具体代码就不附上了，可以杨辉三角打表，也可以组合数学递归 2000的话打表也不是什么问题。

总结：这个题目想了一下午+一晚上，到现在也算是没白费功夫，有点收货，继续加油吧！