链接：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.
题意：
求由n个AB和m个BA组成的长度为2*(n+m)的序列的个数（答案对1e9+7取模）注：AB和BA都是相对位置。
分析：
做法一：组合数求解
用高中组合数的知识试图理解一下。（不成熟的推导过程，仅供参考）
有2*(m+n)个空位放(m+n)个A和(m+n)个B，那么在不考虑序列正确性的前提下，可以构造出的序列总数为：
①
当然这其中包含很多不合条件的错误序列，接下来计算错误的个数；
要求要有n个满足相对位置为AB的字符对，此时我们假定其中有一对的相对位置定为BA，那么剩下的n-1对不管是不是满足相对位置为AB，这个序列都是不成立的，那么就是在定好其中一对的相对位置为BA的情况下，计算出这对BA和剩下n-1对放在2*(m+n)个空位的数量，即：
②
同理，对m对BA可以得出：
③
最终答案就是①-②-③ ；
因为模数1e9+7太大了，所以不能用预处理的组合数计算，要用套Lucas和exgcd的那种。
老实说，我能理解这是为什么，但我不能给出严谨的准确性证明，但是a了，而且跑的飞快（11ms）。qwqqqqq
#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; const int N=1e6+10; typedef long long ll; ll fac[N],inv_fac[N]; void exgcd(ll a, int b, ll& d, ll& x, ll& y) { if(!b) d = a, x = 1, y = 0; else exgcd(b, a%b, d, y, x), y -= x*(a/b); } ll C(int n,int m,int p) { if(m>n) return 0; if(m>n-m) m=n-m; ll ans=1,tmp=1,g,x,y; for(int i=0;i<m;i++)ans=ans*(n-i)%p, tmp=tmp*(i+1)%p; exgcd(tmp,p,g,x,y); return (ans*(x%p)%p+p)%p; } int main() { int n,m; while (~scanf("%d%d",&n,&m)) { ll tmp1=0,tmp2=0; if(n!=0) tmp1=C(2*(n+m),n-1,mod); if(m!=0) tmp2=C(2*(n+m),m-1,mod); ll tmp=C(2*(m+n),n+m,mod); ll ans=((tmp-tmp1-tmp2)%mod+mod)%mod; printf("%lld\n",ans); } return 0; }做法二：DP求解
代码里有注释ovo
#include<bits/stdc++.h> using namespace std; const int maxn=2007; const int mod=1e9+7; int dp[maxn][maxn];//dp[i][j] 有i个A和j个B int main() { int n,m; while (~scanf("%d%d",&n,&m)) { for (int i=0;i<=n+m;i++)//memset超时 for (int j=0;j<=n+m;j++) dp[i][j]=0; dp[0][0]=1;//0个A 0个B 只有一种方案 for (int i=0;i<=n+m;i++) { for (int j=0;j<=n+m;j++) { //填一个A进去 从dp[i-1][j]转移来 //要满足的条件是 此时填入的A小于n个 //或者 已经填入的A的个数减已经填入的B的个数不大于n 满足n个AB（不能超过n） if(i && (i<=n || i-j<=n)) dp[i][j]=(dp[i][j]+dp[i-1][j])%mod; //类似同理 if(j && (j<=m || j-i<=m)) dp[i][j]=(dp[i][j]+dp[i][j-1])%mod; } } printf("%d\n",dp[n+m][n+m]); } return 0; }
