Double Strings

題意：

給你s和t兩個字符串，在其中選出兩個等長的子序列(可以不連續)a，b，滿足a的字典序嚴格小于b的字典序，問方案數,答案mod(1e9+7)

題解：

好的方案的構成是一段相同的前綴+一個不同的字符(a比b小)+長度相同的任意后綴，按照這樣構造一定是合法且包含所有情況
我們用dp[i][j]表示只考慮A的前i個字符和B的前j個字符時的相同的子序列的個數(有點類似于最長公共子序列，不過我們這里記錄的是方案數)
轉移方程可得：dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]（加上之前的情況減去重復的）
當a[i]=b[j]時，dp[i][j]=dp[i-1][j-1]+1
現在是如何求長度相同的任意后綴，我們假設A中剩余長度是x，B中剩余長度位y，設x<=y,那么求長度相同的任意后綴，就是A和B中分別取i個(i最大到x)，有：${\sum }_{i=0}^x{C}_x^i{C}_y^i={\sum }_{i=0}^x{C}_x^{x?i}{C}_y^i=C_{x+y}^x$
每步推導過程都是用的常規組合數公式變換

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); using namespace std; typedef long long ll; typedef pair<int, int> PII; //Fe~Jozky const ll INF_ll=1e18; const int INF_int=0x3f3f3f3f; inline ll read(){ll s=0,w=1ll;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1ll;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10ll+((ch-'0')*1ll),ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } void rd_txt(){#ifdef ONLINE_JUDGE#elsefreopen("in.txt","r",stdin);#endif } const int maxn=1e6+9; const int mod=1e9+7; ll fac[maxn]; ll inv[maxn]; ll dp[6000][6000]; char s[maxn],t[maxn]; int C(int n,int m) {if(n<m) {return 0;}return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod; } ll poww(ll a,ll b){ll ans=1;while(b){if(b&1){ans=ans*a%mod;}a=a*a%mod;b>>=1;}return ans; } void init() {fac[0]=1;int N=1e6;for(int i=1;i<=N;i++) {fac[i]=1LL*fac[i-1]*i%mod;}inv[N-1]=poww(fac[N-1],mod-2);for(int i=N-2;i>=0;i--) {inv[i]=1LL*inv[i+1]*(i+1)%mod;} } int main() {init();scanf("%s%s",s+1,t+1);int n=strlen(s+1),m=strlen(t+1);for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {dp[i][j]=(dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1])%mod;if(s[i]==t[j]) {dp[i][j]=(dp[i][j]+dp[i-1][j-1]+1)%mod;}dp[i][j]=(dp[i][j]+mod)%mod;}}ll ans=0;for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {if(s[i]<t[j]) {ans=(ans+1LL*(dp[i-1][j-1]+1)*C(n-i+m-j,n-i))%mod;}}}cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的Double Strings的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。