这道题不要读假题呀,这道题不是让你选连续的一段(要是连续的一段不就成签到题了么)
dp思路
用
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]表示只考虑
A
A
A中的前
i
i
i个字符和
B
B
B中的前
j
j
j个字符时的相同的子序列的个数。
状态转移如下:
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] − d p [ i − 1 ] [ j − 1 ] dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1] dp[i][j]=dp[i−1][j]+dp[i][j−1]−dp[i−1][j−1]
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]等于不考虑本位的i的情况下的情况数+不考虑本位j的情况下的情况数-这两种情况算重的情况(就是同时不考虑i的本位和j的本位)
当然如果
s
[
i
]
=
=
t
[
j
]
s[i]==t[j]
s[i]==t[j]
那么就是
d
p
[
i
]
[
j
]
+
=
d
p
[
i
−
1
]
[
j
−
1
]
dp[i][j]+=dp[i-1][j-1]
dp[i][j]+=dp[i−1][j−1]
因为如果这种情况的话,那么我们少考虑了一种情况,就是i和j都考虑的情况,那么无论我们前面怎么选,后面加一个
i
i
i位和
j
j
j位就可以了,因此要加上一个
d
p
[
i
−
1
]
[
j
−
1
]
dp[i-1][j-1]
dp[i−1][j−1]这样是我们没有运算到的。
初始化问题
这个待会会再说
右边是不对的初始化,左边是正确的初始化。
求组合数的问题
在正常不卡空间的题里面我们一般会开一个 C [ 5005 ] [ 5005 ] C[5005][5005] C[5005][5005]的数组来记录一下组合数的大小,但是这道题铁定 M L E MLE MLE,因此我觉得那我就用 L u c a s Lucas Lucas定理求组合数,但是 T L E TLE TLE了,这道题应该用阶乘预处理逆元求解组合数。因为模数是素数,因此我们可以用快速幂求解逆元。
递推求组合数
// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
for (int j = 0; j <= i; j ++ )
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
来源:acwing算法基础课
Lucas定理求组合数
若p是质数,则对于任意整数 1 <= m <= n,有:
C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
int qmi(int a, int k, int p) // 快速幂模板
{
int res = 1 % p;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int C(int a, int b, int p) // 通过定理求组合数C(a, b)
{
if (a < b) return 0;
LL x = 1, y = 1; // x是分子,y是分母
for (int i = a, j = 1; j <= b; i --, j ++ )
{
x = (LL)x * i % p;
y = (LL) y * j % p;
}
return x * (LL)qmi(y, p - 2, p) % p;
}
int lucas(LL a, LL b, int p)
{
if (a < p && b < p) return C(a, b, p);
return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
来源:acwing算法基础课
预处理逆元求组合数
昨天其实还挺麻烦的,我是这么搞的:
ll qmi(ll a,ll k,ll p=N) {
ll res=1%p;
while(k){
if(k&1) res=(ll)res*a%p;
a=(ll)a*a%p;
k>>=1;
}
return res;
}
ll lsc[2102100],bym[2021000];
ll C(ll m,ll n,ll p=N)
{
if(n==0)return 1;
if(n==m)return 1;
return lsc[m]*bym[n]%p*bym[m-n]%p;
}
int main(){
lsc[1]=1;
bym[1]=1;
for(int i=2;i<=1000000;i++)
{
lsc[i]=lsc[i-1]*i%N;
bym[i]=qmi(lsc[i],N-2);
}
//C(3,2)=3
//lsc数组是阶乘数组,bym数组是逆元数组
}
当然acwing上也有板子:
首先预处理出所有阶乘取模的余数fact[N],以及所有阶乘取模的逆元infact[N]
如果取模的数是质数,可以用费马小定理求逆元
int qmi(int a, int k, int p) // 快速幂模板
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
ll dp[5002][5002];
char s[5020];
char t[5020];
const ll N=1e9+7;
ll qmi(ll a,ll k,ll p=N) {
ll res=1%p;
while(k){
if(k&1) res=(ll)res*a%p;
a=(ll)a*a%p;
k>>=1;
}
return res;
}
ll lsc[2102100],bym[2021000];
ll C(ll m,ll n,ll p=N)
{
if(n==0)return 1;
if(n==m)return 1;
return lsc[m]*bym[n]%p*bym[m-n]%p;
}
int main(){
cin>>s+1>>t+1;
lsc[1]=1;
bym[1]=1;
for(int i=2;i<=1000000;i++)
{
lsc[i]=lsc[i-1]*i%N;
bym[i]=qmi(lsc[i],N-2);
}
int n=strlen(s+1);
int m=strlen(t+1);
ll ans=0;
dp[0][0]=1;
for(int i=1;i<=n;i++){
dp[i][0]=1;
for(int j=1;j<=m;j++){
dp[0][j]=1;
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
dp[i][j]%=N;
if(s[i]==t[j]){
dp[i][j]+=dp[i-1][j-1];
dp[i][j]%=N;
}else if(s[i]<t[j]){
ans+=(ll)(dp[i-1][j-1]*C(n+m-i-j,n-i))%N;
/*cout<<i<<" "<<j<<"--------";
cout<< C(n+m-i-j,n-i)<<endl;*/
}
if(dp[i][j]<=0)dp[i][j]+=N;
}
}
ans%=N;
cout<<ans<<endl;
}