2021牛客多校5 Double Strings

Double Strings

题意：
给你两个字符串$s$和$t$,长度都小于等于5000，求有多少种子序列，使得s和t的子序列长度相同， 但是$s$的子序列组成的字符串的字典序比 $t$ 的小。
思路:
字典序小，即前缀相同的部分，有一位的字典序小，之后只要取长度相同即可。
我们可以用 dp[$i$] [$j$],来预处理出，$s$的前$i$位，和$t$的前$j$位，前缀相同的方案数。
转移方程即为：
dp[$i$] [$j$] = dp[$i$ - 1] [$j$] + dp [$i$] [$j$ - 1] - dp[$i$ - 1] [$j$ - 1]；
像最长公共子序列的转移方程,前面的情况相加再减去重复部分。
当s[$i$] == t[$j$]时，dp[$i$] [$j$] = dp[$i$ - 1] [$j$ - 1] + 1;
现在是如何求长度相同的任意后缀，我们假设$s$中剩余长度是$x$，$t$中剩余长度位$y$，设$x$<=$y$,那么求长度相同的任意后缀，就是$s$和$t$中分别取$i$个($i$最大到$x$)，有：
最后一步变换用到了范德蒙的卷积公式。
然后就欢乐AC了。

#include<bits/stdc++.h>
using namespace std;
#define ll long longconst 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;
}