题意:

给你两个数字n， m, 分别是字符串s,t各自的长度，请问有多少个比t字典序大的s的子序列

题目链接：

https://ac.nowcoder.com/acm/contest/885/G

题解：

要选字典序大的，那么我们有两种选取情况

  • 选长度比他长的，肯定是可以的，我们可以枚举第一个字符的位置，这样后面的数字随便取，只要总长度超过m肯定没问题，则说明后面至少要取m个，可以用组合数学求
  • 选长度和他相等的，那么就要进行DP。dp[i][j]  表示 s串中前i个数字选择了j个比 t串前j个数字大的方案数； f[i][j] 表示  s串中前i个数字选择了j个与t串前j个数字一样大的方案数； 状态转移为：当 s 串第i个数字没被选的时候，d[i][j] = d[i-1][j]，f[i][j] = f[i - 1][j]；当 s 串第i个数字被选的时候，dp[i][j] += dp[i-1][j-1]，如果s[i] > t[j]，那么d[i][j] += f[i-1][j-1]，如果s[i] = t[j]，那么f[i][j] += f[i-1][j-1]。

AC_code:

#include<bits/stdc++.h>
using namespace std;
#define maxn 3005
#define mod 998244353
char s[maxn], t[maxn];
int c[maxn][maxn], dp[maxn][maxn], f[maxn][maxn];

void add(int &x, int y) {
	x = (x + y) % mod;
}

void init() { //组合数预处理
	/*
	c[i][j] 代表  i个数里面取至少j个数字的方案数
	*/
	c[0][0] = 1;
	for(int i = 1; i <= 3000; i++) {
		c[i][0] = c[i][i] = 1;
		for(int j = 1; j < i; j++) {
			add(c[i][j], c[i-1][j-1]+c[i-1][j]);
		}
	}
	for(int i = 1; i<= 3000; i++) {
		for(int j = i; j >= 0; j--) {
			add(c[i][j], c[i][j+1]);
		}
	}
}
int main() {
	int T, n, m;
	init();
	scanf("%d", &T);
	while(T--) {
		scanf("%d %d", &n, &m);
		scanf("%s %s", s+1, t+1);
		int ans = 0;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				dp[i][j] = f[i][j] = 0;
			}
		}
		for(int i = 1; i <= n; i++) {
			f[i-1][0] = 1;
			if(s[i] != '0' && (n-i+1 > m)) { //枚举首个字母的位置 且不为0
				add(ans, c[n-i][m]);//后面的数字随便取
			}
			for(int j = 1; j <= min(i, m); j++) {
				add(f[i][j], f[i-1][j]);
				add(dp[i][j], dp[i-1][j]);
				add(dp[i][j], dp[i-1][j-1]);
				if (s[i] > t[j]) {
					add(dp[i][j], f[i-1][j-1]);
				} else if (s[i] == t[j]) {
					add(f[i][j], f[i-1][j-1]);
				}
			}
		}
		add(ans, dp[n][m]);
		printf("%d\n", ans);
	}
}