（2021牛客多校五）D-Double Strings（乘法原理+动态规划）

 题意：给出两个字符串a和b，求出a和b中子串长度相同且a中子串字典序小于b中子串字典序的子串对个数。

分析：设f[i][j]表示第一个字符串前i个字符中第二个字符串前j个字符中的相同子序列的数量

先来说一下这个更新方式，假如我们当前枚举到字符串a的第i个位置以及字符串b的第j个位置

如果a[i]!=b[j] 那么有f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]

f[i-1][j]包含了b串中第j个字符串参与匹配的相同子序列，而f[i][j-1]包含了a串中第i个字符串参与匹配的相同子序列，但是两者都包含了f[i-1][j-1]，所以会有一次重复计算

如果a[i]==b[j] 那么有f[i][j]=f[i-1][j]+f[i][j-1]

a[i]==b[j]时的更新就会比a[i]!=b[j]时的情况多一个a串中第i个字符串与b串中第j个字符串相匹配的情况，这样的情况数是f[i-1][j-1]，所以动态转移方程就是f[i][j]=f[i-1][j]+f[i][j-1]

那这样我们再重新遍历一次a串和b串，当a[i]<b[j]时，a串的前i-1个字符和b串的前j-1个字符中的匹配数就是f[i-1][j-1]，a第i个字符后面还有n-i个字符，b串第j个字符后面还有m-j个字符，我们可以任意从a串的后面字符中选取x个，也从b串的后面字符中选取x个，也就是说选取方案数是,这个等式可以变形为

这就等价于C(n-i+m-j,n-i)。

等价解释：有一个长度为n-i的字符串和一个长度为m-j的字符串以及一个长度为n-i+m-j的字符串，我们从一个长度为n-i+m-j的字符串中取出n-i的方案数等价于从一个长度为n-i的字符串中取出n-i-x个字符串以及从一个长度为m-j的字符串中取出x个字符串的方案数，遍历所有的x并求和即可。

于是在我们遍历a串和b串时，当a[i]<b[j]时，这个字符对的贡献就是f[i-1][j-1]*C(n-i+m-j,n-i),记录到答案内即可。

由于我们涉及到组合取模，所以我们需要处理一下阶乘以及阶乘的逆元，细节见代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=1e4+10,mod=1e9+7;
typedef long long ll;
ll f[N][N];//f[i][j]表示第一个字符串前i个字符中第二个字符串前j个字符中的相同子序列的数量 
char a[N],b[N]; 
ll fac[N],inv[N];
ll qmi(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
ll C(ll n,ll m)
{
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
	scanf("%s",a+1);
	scanf("%s",b+1);
	ll n=strlen(a+1),m=strlen(b+1);
	fac[0]=inv[0]=1;
	for(int i=1;i<=m+n;i++)
	{
		fac[i]=fac[i-1]*i%mod;
		inv[i]=qmi(fac[i],mod-2)%mod;
	}
	for(int i=0;i<=max(n,m);i++)
		f[i][0]=f[0][i]=1;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		if(a[i]==b[j]) f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
		else f[i][j]=(f[i-1][j]+f[i][j-1]-f[i-1][j-1]+mod)%mod;
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		if(a[i]<b[j])
		ans=(ans+f[i-1][j-1]*C(n-i+m-j,n-i))%mod;
	cout<<ans;
	return 0;
}