题意：（n+m）个A，（n+m）个B组成一个字符串，将其剖开，使其有n个AB和m个BA的方案数
思路1：DP，dp[i][j]表示以i个A开头，j个B开头的方案数。
如果当前这位是A，则其要满足，i-j<=n,AB的个数不能超过（n+1）
B的情况同理。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 1e9+7; int n,m,f[3010][3010]; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int sum(int a, int b) { int s = (a + b); if (s >= mod) s -= mod; return s; } void init() { rep(i,0,n+m) rep(j,0,n+m) f[i][j]=0; f[0][0]=1; rep(i,0,n+m) rep(j,0,n+m) { if(i-j<=n&&i!=0) f[i][j]=sum(f[i][j],f[i-1][j]); if(j-i<=m&&j!=0) f[i][j]=sum(f[i][j],f[i][j-1]); //printf("i=%d j=%d %d ",i,j,f[i][j]); } printf("%d ",f[n+m][n+m]); } int main() { while(~scanf("%d%d",&n,&m)) { init(); } }
思路2：组合数
ans=C（2*（n+m），n+m）- C（2*（n+m），n-1）-C（2*（n+m），m-1）
C（2*（n+m），n-1）的含义是
我们有（n+m+m+1）个A，和（n-1）个B，排列一下的方案数。
选取A和B的差数为（2*m+2）的前缀，AB互换，就是不合法答案。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 1e9+7; int n,m; ll fac[10100],inv[10100]; int sum(int a, int b) { int s = (a + b); if (s >= mod) s -= mod; return s; } int sub(int a, int b) { int s = a - b; if (s < 0) s += mod; return s; } int mult(int a, int b) { return (1LL * a * b) % mod; } ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll qpow(ll a,ll b,ll p) { ll ret=1;a%=p; while(b) { if(b&1) ret=ret*a%p; b/=2;a=a*a%p; } return ret; } ll C(ll n,ll m) { if(m>n) return 0; return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod; } int main() { fac[0]=1;inv[0]=1; for(int i=1;i<=10000;i++) { fac[i]=1ll*fac[i-1]*i%mod; inv[i]=qpow(fac[i],mod-2,mod); } while(~scanf("%d%d",&n,&m)) { printf("%d ",sub(sub(C(2*(n+m),n+m),C(2*(n+m),n-1)),C(2*(n+m),m-1))); } }