(2021 Niuke multi school V) d-double strings (multiplication principle + dynamic programming)

  The question ： Give me two strings a and b, Find out a and b Neutron strings have the same length and a The neutron string dictionary order is less than b Number of substring pairs of substring dictionary order .

analysis ： set up f[i][j] Before the first string i Before the second string of characters j The number of identical subsequences in characters

Let's talk about this update method first , Suppose we enumerate the string currently a Of the i Positions and strings b Of the j A place

If a[i]!=b[j] So there are f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]

f[i-1][j] Contains b The second in the series j Strings participate in the same subsequence of matching , and f[i][j-1] Contains a The second in the series i Strings participate in the same subsequence of matching , But both contain f[i-1][j-1], So there will be a double calculation

If a[i]==b[j] So there are f[i][j]=f[i-1][j]+f[i][j-1]

a[i]==b[j] The update will be better than a[i]!=b[j] When the situation is one more a The second in the series i A string and b The second in the series j String matching , The number of such cases is f[i-1][j-1], So the dynamic transfer equation is f[i][j]=f[i-1][j]+f[i][j-1]

So let's go over it again a String sum b strand , When a[i]<b[j] when ,a Before the string i-1 Characters and b Before the string j-1 The number of matches in characters is f[i-1][j-1],a The first i Characters followed by n-i Characters ,b Serial number j Characters followed by m-j Characters , We can choose from a Select from the following characters of the string x individual , Also from the b Select from the following characters of the string x individual , That is to say, the number of schemes selected is , This equation can be transformed into

This is equivalent to C(n-i+m-j,n-i).

Equivalent interpretation ： There is a length of n-i And a string of length m-j String and a length of n-i+m-j String , We start from a length of n-i+m-j From the string of n-i The number of schemes is equivalent to from a length of n-i From the string of n-i-x String and from a length of m-j From the string of x Number of schemes of strings , Traverse all x And sum .

So before we traverse a String sum b String time , When a[i]<b[j] when , The contribution of this character pair is f[i-1][j-1]*C(n-i+m-j,n-i), Record it in the answer .

Because we are concerned with modular combination , So we need to deal with factorials and the inverse of factorials , See code for details ：

#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] Before the first string i Before the second string of characters j The number of identical subsequences in characters  
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;
}