題目鏈接：點擊查看

題目大意：給出兩個字符串 $s$ 和 $t$，要求 “一段相同的前綴” + “一個不同的字符(滿足s[i]<t[j])”+ “長度相同的任意后綴” 的組成方案數，其中可以選取 $s$ 和 $t$ 的子序列用于構成

題目分析：類比于最長公共子序列，這里將 $dp[i][j]$ 定義為，由字符串 $s[1:i]$ 和 $t[1:j]$ 組成的相同前綴的個數，其實也就是方案數，轉移的話 $dp[i][j]=dp[i?1][j]+dp[i][j?1]?dp[i?1][j?1]$，當 $s[i]=t[j]$ 時還要加上 $dp[i?1][j?1]+1$，這些類比于 $lcs$ 的求解過程很容易想到

這個題的瓶頸就是如何去求 “長度相同的任意后綴”，假設 $last[x][y]$ 的意義是，長度為 $x$ 的字符串和長度為 $y$ 的字符串，組成 “長度相同的任意后綴” 的方案數。不妨設 $x<=y$，那么按照長度枚舉展開就是 $C(x,1)?C(y,1)+C(x,2)?C(y,2)+...+C(x,x)?C(y,x)=\sum _{k=1}^{x}C(x,k)?C(y,k)$，這里根據 $C(n,m)=C(n,n?m)$ 做一下轉換，即 $\sum _{k=1}^{x}C(x,k)?C(y,k)=\sum _{k=1}^{x}C(x,x?k)?C(y,k)$，根據范德蒙德卷積公式推得原式等于 $C(x+y,x)$

如此一來，預處理出上述的 $dp$ 和 $last$ 數組，就可以去枚舉中間的斷點，也就是 “一個不同的字符(滿足s[i]<t[j])” ，然后根據乘法原理計算貢獻了

代碼：

// Problem: Double Strings // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11256/D // Memory Limit: 524288 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=5e3+100; const int M=1e6+100; const int mod=1e9+7; char s[N],t[N]; int dp[N][N]; int fac[M],inv[M]; int q_pow(int a,int b) {int ans=1;while(b) {if(b&1) {ans=1LL*ans*a%mod;}a=1LL*a*a%mod;b>>=1;}return ans; } int C(int n,int m) {if(n<m) {return 0;}return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod; } void init() {fac[0]=1;for(int i=1;i<M;i++) {fac[i]=1LL*fac[i-1]*i%mod;}inv[M-1]=q_pow(fac[M-1],mod-2);for(int i=M-2;i>=0;i--) {inv[i]=1LL*inv[i+1]*(i+1)%mod;} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);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; }

總結

以上是生活随笔為你收集整理的2021牛客多校5 - Double Strings(dp+组合数学)的全部內容，希望文章能夠幫你解決所遇到的問題。

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