subsequence 1

Posted on | In , , ,

题目链接

题意

有两个字符串$S,T$，询问有多少个$S$的子序列比$T$串大。

思路

$S$的长度比$T$大的一定大，所以可以先找出这样的子序列数量。
若长度相等，那么一定从某一个位置开始$S$比$T$大。
$dp[i][j]$表示$S$串以$i$开头有多少个子序列比$T$串以$j$开头的子串大。
转移方程见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
const int N = 3005;
ll dp[N][N];
const ll mod = 998244353;
ll C[N][N], sum[N][N];
char s[N], t[N];
int main()
{
    C[0][0] = 1;
    for (int i = 1; i <= 3000; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    sum[0][0] = 1;
    for (int i = 1; i <= 3000; i++)
    {
        sum[i][0] = 1;
        for (int j = 1; j <= i; j++)
            sum[i][j] = (sum[i][j - 1] + C[i][j]) % mod;
    }
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        scanf("%s%s", s, t);
        for (int i = 0; i <= n + 2; i++)
            for (int j = 0; j <= m + 2; j++)
                dp[i][j] = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = m - 1; j >= 0; j--)
            {
                if (s[i] == t[j])
                {
                    dp[i][j] = dp[i + 1][j + 1];
                }
                else if (s[i] < t[j])
                {
                    dp[i][j] = 0;      
                }
                else
                {
                    dp[i][j] = C[n - i - 1][m - j - 1];
                }
                dp[i][j] = (dp[i + 1][j] + dp[i][j]) % mod;
            }
        }
        ll ans = 0;
        for(int i=0;i < n - m;i++)
        {
            if(s[i] != '0')
            {
                ans = (ans + mod + sum[n-i-1][n-i-1] - sum[n-i-1][m-1]) % mod;
              //  cout<<ans<<' '<<i<<endl;
            }
            else continue;
        }
        printf("%lld\n", (ans + dp[0][0]) % mod);
    }
    return 0;
}

0%