2021 Niuke multi school 5 double strings

Double Strings

The question ：
Here are two strings $s$ and $t$, The length is less than or equal to 5000, Find out how many seed sequences there are , bring s and t The length of the subsequence is the same , however $s$ The lexicographic order ratio of a string composed of subsequences of $t$ Small .
Ideas :
The dictionary order is small , That is, the parts with the same prefix , There is a little dictionary order , Then just take the same length .
We can use dp[$i$] [$j$], To preprocess out ,$s$ Before $i$ position , and $t$ Before $j$ position , The number of schemes with the same prefix .
The transfer equation is ：
dp[$i$] [$j$] = dp[$i$ - 1] [$j$] + dp [$i$] [$j$ - 1] - dp[$i$ - 1] [$j$ - 1];
Like the transfer equation of the longest common subsequence , Add the previous cases and subtract the repeated parts .
When s[$i$] == t[$j$] when ,dp[$i$] [$j$] = dp[$i$ - 1] [$j$ - 1] + 1;
Now how to find Any suffix of the same length , We assume that $s$ The remaining length in is $x$,$t$ Remaining length bits in $y$, set up $x$<=$y$, Then find any suffix with the same length , Namely $s$ and $t$ Take $i$ individual ($i$ Maximum to $x$), Yes ：
The last step of transformation uses van der Monde's convolution formula .
And then it's fun AC 了 .

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=100010,INF=1e9;
const ll mod=1e9+7;
ll qp(ll n,ll m){
    
	ll ans=1;
	while(m){
    
		if(m%2==1)ans=ans*n%mod;
		n=n*n%mod;
		m/=2;
	}
	return ans;
}
ll n,m;
ll dp[5005][5005];
ll fac[10004];
ll inv[10004];
void init(){
    
	fac[1]=1;fac[0]=1;
	for(int i=2;i<=10000;i++)fac[i]=fac[i-1]*i%mod;
	inv[10000]=qp(fac[10000],mod-2)%mod;
	for(int i=9999;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod; 
}
ll C(int n,int m){
    
	if(n<m)return 0;
	else {
    
		return fac[n]*inv[n-m]%mod*inv[m]%mod;
	}
}
char s[5005],t[5004]; 
int main(){
    
	init();
	scanf("%s%s",s+1,t+1);
	int len1=strlen(s+1),len2=strlen(t+1);
	for(int i=1;i<=len1;i++){
    
		for(int j=1;j<=len2;j++){
    
			dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
			dp[i][j]%=mod;
			if(s[i]==t[j]){
    
				dp[i][j]+=dp[i-1][j-1]+1;
			}
			dp[i][j]=(dp[i][j]%mod+mod)%mod;
		}
	}
	ll ans=0;
	for(int i=1;i<=len1;i++){
    
		for(int j=1;j<=len2;j++){
    
			if(s[i]<t[j]){
    
				ans=(ans+(dp[i-1][j-1]+1)%mod*C(len1-i+len2-j,len1-i)%mod)%mod;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}