upc-2021个人训练赛第27场 K: ABBA （组合数学）

问题 K: ABBA
时间限制: 1 Sec 内存限制: 128 MB

题目描述
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).
输入
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≤103
• There are at most 2019 test cases, and at most 20 of them has max{n,m}>50.
  输出
  For each test case, print an integer which denotes the result.
  样例输入 Copy
  1 2
  1000 1000
  0 0
  样例输出 Copy
  13
  436240410
  1

思路：

考虑用总的方案数减去不合法的方案数。
比如说第一个样例，考虑极端的情况(AAABBB)
这种情况是不合法的，因为(B)后面没有足够的(A)来构成(BA)组合。
移动一个(A)到任意的地方，都是不合法的，比如(AABABB,AABBAB,AABBBA).
也就是说，为了凑成不合法的(BA),最多可以将(m-1)的(A)任意排列，方案数为(c[2n+2m][m-1])
另一个不合法的方案数也同上。
注意只有(>0)的时候才有不合法的方案数。

代码：

ll ksm(ll a,ll b,ll p){
    ll res=1;
    while(b){
//&运算当相应位上的数都是1时，该位取1，否则该为0。
        if(b&1)
            res=1ll*res*a%p;//转换为ll型
        a=1ll*a*a%p;
        b>>=1;//十进制下每除10整数位就退一位 
    }
    return res;
}
 
const ll mod=1e9+7;
const int N=4100;
 
ll fact[N];//阶乘 
ll infact[N];//逆元 
 
void init(){
    fact[0]=1;
    infact[0]=1;
    for(int i=1;i<N;i++){
        fact[i]=fact[i-1]*i%mod;
        infact[i]=infact[i-1]*ksm(i,mod-2,mod)%mod;
    }
}
 
ll cul(ll a,ll b){
    return fact[a]%mod*infact[b]%mod*infact[a-b]%mod;
}
 
void solve(){
    ll n,m;
    while(scanf("%lld%lld",&n,&m)!=EOF){
        ll t=2*n+2*m;
        ll ans=cul(t,n+m);
        if(n) ans=(ans-cul(t,n-1)+mod)%mod;
        if(m) ans=(ans-cul(t,m-1)+mod)%mod;
        printf("%lld
",ans);
    }   
}