做的网站如何全屏代码,成都企业建站系统,项目招商,教做面点的网站D-Double Strings fi,jf_{i,j}fi,j表示a中前i个字符#xff0c;b中前j个字符相同子序列的数量#xff0c;容斥转移 fi,jfi−1,jfi,j−1−fi−1,j−1{(1fi−1,j−1)[aiaj]}f_{i,j}f_{i-1,j}f_{i,j-1}-f_{i-1,j-1}\{(1f_{i-1,j-1})[a_ia_j]\}fi,jfi−1,jfi,j−1−fi−1…D-Double Strings fi,jf_{i,j}fi,j表示a中前i个字符b中前j个字符相同子序列的数量容斥转移
fi,jfi−1,jfi,j−1−fi−1,j−1{(1fi−1,j−1)[aiaj]}f_{i,j}f_{i-1,j}f_{i,j-1}-f_{i-1,j-1}\{(1f_{i-1,j-1})[a_ia_j]\}fi,jfi−1,jfi,j−1−fi−1,j−1{(1fi−1,j−1)[aiaj]}
gi,jg_{i,j}gi,j表示a中前i个字符b中前j个字符满足小于关系子序列的数量
类似相同子序列数量转移即可。 gi,jgi−1,jgi,j−1−gi−1,j−1(1gi−1,j−1){(fi−1,j−11)[aiaj]}g_{i,j}g_{i-1,j}g_{i,j-1}-g_{i-1,j-1}(1g_{i-1,j-1})\{(f_{i-1,j-1}1)[a_ia_j]\}gi,jgi−1,jgi,j−1−gi−1,j−1(1gi−1,j−1){(fi−1,j−11)[aiaj]}
Code1
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
const int N5010;
const ll mod1000000007;
char a[N],b[N];
int f[N][N],g[N][N];
int n,m;
int main()
{scanf(%s%s,a1,b1);nstrlen(a1);mstrlen(b1);for(int i1;in;i)for(int j1;jm;j){if(a[i]b[j])f[i][j](1ll*f[i-1][j]f[i][j-1]1)%mod;elsef[i][j](1ll*modf[i-1][j]f[i][j-1]-f[i-1][j-1])%mod;}for(int i1;in;i)for(int j1;jm;j){if(a[i]b[j]) g[i][j](1ll*g[i-1][j]g[i][j-1]1f[i-1][j-1])%mod;elseg[i][j](1ll*g[i-1][j]g[i][j-1])%mod;}printf(%lld\n,g[n][m]);
}Code2
首先求出相同子序列然后枚举哪个位置不同即第一个aiaja_ia_jaiaj然后利用下面公式加快计算。
∑0≤i≤k(ni)(mk−i)(nmk)\sum_{0\leq i\leq k}\dbinom{n}{i}\dbinom{m}{k-i}\dbinom{nm}{k}0≤i≤k∑(in)(k−im)(knm)
于是有 ∑0≤i≤m(ni)(mi)∑0≤i≤m(ni)(mm−i)(nmm)\sum_{0\leq i\leq m}\dbinom{n}{i}\dbinom{m}{i}\sum_{0\leq i\leq m}\dbinom{n}{i}\dbinom{m}{m-i}\dbinom{nm}{m}0≤i≤m∑(in)(im)0≤i≤m∑(in)(m−im)(mnm)
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
const int N5010;
const int mod1000000007;
char a[N],b[N];
int f[N][N];
int n,m;
int fac[N1],inv[N1];
ll qmi(ll a,ll b){ll v1;while(b){if(b1) vv*a%mod;aa*a%mod;b1;}return v;}
void init()
{fac[0]1;for(int i1;i10000;i) fac[i]1ll*fac[i-1]*i%mod;inv[10000]qmi(fac[10000],mod-2);for(int i9999;i0;i--) inv[i]1ll*inv[i1]*(i1)%mod;
}
int C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main()
{init();scanf(%s%s,a1,b1);nstrlen(a1);mstrlen(b1);for(int i1;in;i)for(int j1;jm;j){if(a[i]b[j])f[i][j](1ll*f[i-1][j]f[i][j-1]1)%mod;elsef[i][j](1ll*modf[i-1][j]f[i][j-1]-f[i-1][j-1])%mod;}ll ans0;for(int i1;in;i)for(int j1;jm;j)if(a[i]b[j])ans(ans1ll*(f[i-1][j-1]1)*C(n-im-j,n-i)%mod)%mod;printf(%lld\n,ans);
}
