2021牛客暑期多校训练营5 D. Double Strings（DP/排列组合）

本文主要是介绍2021牛客暑期多校训练营5 D. Double Strings（DP/排列组合），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/contest/11256/D
来源：牛客网

题目描述

Given two strings A,BA,B, and little H wants to choose a subsequence from {1,2,⋯ ,∣A∣}{1,2,⋯,∣A∣}(call it aa) and from {1,2,⋯ ,∣B∣}{1,2,⋯,∣B∣}(call it bb) respectively. A scheme is called good iff ∣a∣=∣b∣∣a∣=∣b∣ and ∃i∈{1,2,⋯ ,∣a∣},Aai<Bbi,∀j∈{1,2,⋯ ,i−1},Aaj=Bbj∃i∈{1,2,⋯,∣a∣},Aai<Bbi,∀j∈{1,2,⋯,i−1},Aaj=Bbj. Print the number of good schemes modulo 109+7109+7.

输入描述:

The first line contains a string A (1≤∣A∣≤5000)A (1≤∣A∣≤5000).

The second line contains a string B (1≤∣B∣≤5000)B (1≤∣B∣≤5000).

It's guaranteed that AA and BB only contain lowercase letters.

输出描述:

Output one line only containing one integer, denoting the answer.

示例1

输入

复制

ib
coe

输出

复制

5

说明

For the first case, the 5 good schemes are:

A={1} (i),B={2} (o)A={1} (i),B={2} (o)
A={2} (b),B={1} (c)A={2} (b),B={1} (c)
A={2} (b),B={2} (o)A={2} (b),B={2} (o)
A={2} (b),B={3} (e)A={2} (b),B={3} (e)
A={1,2} (ib),B={2,3} (oe)A={1,2} (ib),B={2,3} (oe)

示例2

输入

复制

banana
apple

输出

复制

273

题意大概是让选择两个等长子序列（可以不连续）构成一个scheme，对于这两个子序列中的一个位置i的元素有\(A[a[i]]<B[b[i]]\)，然后两个子序列前半部分的元素为下标对应的两个串中的字符相等，后半部分任意，问有多少个good scheme。

这实际上就是枚举A和B中的两个位置i，j满足\(A[i] < B[j]\)，然后把前半部分两个串的所有公共子序列个数求出来，乘以后半部分所有的选法加到答案即可。首先看前半部分怎么算。求两个串的公共子序列的个数自然是用DP。设\(dp[i][j]\)表示A串到i，B串到j（不一定取到）的公共子序列的数量。有转移方程：

	for(int i = 1; i <= len1; i++) {
		for(int j = 1; j <= len2; j++) {
			if(s1[i] == s2[j]) {
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + 1) % mod;//实际上是dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + dp[i - 1][j - 1] + 1
			} else {
				dp[i][j] = ((dp[i - 1][j] + dp[i][j - 1]) % mod + mod - dp[i - 1][j - 1]) % mod;
			}
		}
	}

减去dp[i - 1, j - 1]是因为这一部分被重复加了一次。s1[i] == s2[j]时加的1是指公共子序列为s1[i]的这一种情况。之所以要把dp[i - 1, j - 1]是因为这一部分可以和s1[i]组成新的公共子序列。注意有可能减出来负数，要多加模数。

处理出dp数组以后则开始遍历A[i] < B[j]的位置，枚举到一个合法的位置时，就可以计算后半部分的可能的情况数了。由题意。后半部分两个子序列应该长度相等，所以情况数用组合数计算为：\(C_n^0C_m^0 + C_n^1C_m^1+...C_n^{min(n, m)}C_m^{min(n, m)}\)。设\(m\leq n\)，则变为\(C_n^0C_m^m + C_n^1C_m^{m - 1}+...C_n^mC_m^0\)，可以看做是从两个分别有n个球和m个球的盒子里总共取m个球的方案数，即\(C_{n + m}^m\)，算出来即可。

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
#define int long long
string s1, s2;
long long dp[5005][5005];//dp[i][j]表示s1中到i的子串，s2中到j的子串的公共子序列的数量
int len1, len2;
#define LL long long
#define p 1000000007
const int maxn=2000005;
void extend_gcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1,y=0;
        return;
    }
    extend_gcd(b,a%b,y,x);
    y-=a/b*x;
}
LL inv[maxn+10];
LL f[maxn+10];
void init(){//阶乘及其逆元打表
    f[0]=1;
    for(int i=1;i<=maxn;i++){
        f[i]=f[i-1]*i%p;
    }

    LL x,y;
    extend_gcd(f[maxn],p,x,y);//先求出f[N]的逆元，再循环求出f[1~N-1]的逆元
    inv[maxn]=(x%p+p)%p;
    for(int i=maxn-1;i>=1;i--){
        inv[i]=inv[i+1]*(i+1)%p;
    }
}

LL C(LL n,LL m){
    if(n==m||m==0)return 1;
    if(m > n) return 0;
    return (f[n]*inv[m]%p*inv[n-m]%p)%p;
}
signed main() {
	cin >> s1;
	cin >> s2;
	len1 = s1.size();
	len2 = s2.size();
	s1 = " " + s1;
	s2 = " " + s2;
	init();
	//dp[i][j]表示s1中到i的子串，s2中到j的子串的公共子序列的数量
	for(int i = 1; i <= len1; i++) {
		for(int j = 1; j <= len2; j++) {
			if(s1[i] == s2[j]) {
				//可能出现负数 防爆模
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + 1) % mod;
			} else {
				dp[i][j] = ((dp[i - 1][j] + dp[i][j - 1]) % mod + mod - dp[i - 1][j - 1]) % mod;
			}
		}
	}
	long long ans = 0;
	for(int i = 1; i <= len1; i++) {
		for(int j = 1; j <= len2; j++) {
			if(s1[i] < s2[j]) {
				long long n = len1 - i, m = len2 - j;
				ans = (ans + (dp[i - 1][j - 1] + 1ll) * C(1ll * n + m, 1ll * min(n, m)) % mod) % mod;
			}
		}
	}
	cout << ans;
	return 0;
}

这篇关于2021牛客暑期多校训练营5 D. Double Strings（DP/排列组合）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！