分析
考虑 DP。
定义状态函数 $f_{i,j}$ 表示在 $s[1\dots i]$ 中选一个子串 $a$,在 $t[1 \dots j]$ 中选一个子序列 $b$,且 $s_i,t_j$ 必选时 $a=b$ 的方案数。则有两种情况:
- $s_i \ne t_j$。此时 $a$ 和 $b$ 是不可能相同的了,所以 $f_{i,j}=0$。
- $s_i = t_j$。在只选 $s_i,t_j$ 时有 $1$ 种方案,而不止选 $s_i,t_j$ 时根据枚举前一个字符选的位置,有 $\sum\limits_{k=1}^{j-1} f_{i-1,k}$ 种方案。所以 $f_{i,j}=1+\sum\limits_{k=1}^{j-1} f_{i-1,k}$。
整合一下有转移方程:$f_{i,j}=[s_i=t_j]\times(\sum\limits_{k=1}^{j-1}f_{i-1,k}+1)$。定义 $s_{i,j}=\sum\limits_{k=1}^{j} f_{i,k}$,则有:$f_{i,j}=[s_i=t_j]\times(s_{i,j-1}+1)$。这就是个前缀和优化,在更新完 $f_{i,j}$ 只后直接更新 $s_{i,j}$ 即可。
答案就是 $\sum\limits_{i=1}{|s|}\sum\limits_{j=1}f_{i,j}$。复杂度 $O(n^2)$。
代码
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")
namespace yzqwq{
il int read(){
int x=0,f=1;char ch=gc;
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
return x*f;
}
il int qmi(int a,int b,int p){
int ans=1;
while(b){
if(b&1) ans=ans*a%p;
a=a*a%p,b>>=1;
}
return ans;
}
il auto max(auto a,auto b){return (a>b?a:b);}
il auto min(auto a,auto b){return (a<b?a:b);}
il int gcd(int a,int b){
if(!b) return a;
return gcd(b,a%b);
}
il int lcm(int a,int b){
return a/gcd(a,b)*b;
}
il void exgcd(int a,int b,int &x,int &y){
if(!b) return x=1,y=0,void(0);
exgcd(b,a%b,x,y);
int t=x;
x=y,y=t-a/b*x;
return ;
}
mt19937 rnd(time(0));
}
using namespace yzqwq;
const int N=5005,p=1e9+7;
int f[N][N],s[N][N];
char a[N],b[N];
int n,m;
il void solve(){
scanf("%s",a+1),n=strlen(a+1);
scanf("%s",b+1),m=strlen(b+1);
for(re int i=1;i<=n;++i)
for(re int j=1;j<=m;++j){
f[i][j]=(long long)((a[i]==b[j])*(s[i-1][j-1]+1))%p;
s[i][j]=(long long)(s[i][j-1]+f[i][j])%p;
}
long long ans=0;
for(re int i=1;i<=n;++i) ans=(ans+s[i][m])%p;
printf("%lld\n",ans);
return ;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int t=1;while(t--)
solve();
return 0;
}
标签:ch,limits,题解,sum,Substring,il,auto,CF163A,define
From: https://www.cnblogs.com/harmisyz/p/18054664