牛客noip2018练习赛5 C串串

题意：

告诉你S，T分别有多少01，问多少对S，T满足T是S的子序列。

题解：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
const LL mod=1e9+7;
LL a,b,c,d,ans,C[4010][4010];
void pre()
{
	for(LL i=0;i<=4000;i++)
	{
		C[i][0]=1;
		for(LL j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
}
LL calc(LL x,LL y)
{
	if(x==0) return 1;
	if(y==0) return 0;
	return C[x+y-1][y-1];
}
int main()
{
	pre();
	scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
	a-=c;b-=d;LL ans=0;
	for(LL i=0;i<=a;i++)
		for(LL j=0;j<=b;j++)
		{
			LL t1=a-i,t2=b-j;
			(ans+=C[i+j][i]*calc(t2,c)%mod*calc(t1,d)%mod)%=mod;
		}
	printf("%lld",ans*C[c+d][d]%mod);
}