2019牛客第五场G题 (subsequence 1) DP

题意：给一个数字字符串s和t，求s中有多少个子序列比t更大

题解：如果子序列比t更长，那么只要开头不是0都可以，暴力枚举做这件事就好了。问题在于子序列和t等长的情形。从前往后考虑很麻烦，试着从后往前考虑：dp[i][j] 表示的是s中以i开始的后缀的子序列匹配了t的j以后的子串。

于是有:
$$
dp[i][j]=
\begin{cases}
dp[i + 1][j] + dp[i + 1][j + 1] & s[i]=t[j]\
dp[i + 1][j] + C(n - i, m - j)& s[i]>t[j]\
dp[i + 1][j]& s[i]<t[j]

\end{cases}
$$
每次转移都是的，然后这个题就做完了。

#include <algorithm>
#include <iostream>
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
const int maxn = 3005;
char s[maxn], t[maxn];
using namespace std;
using ll = long long;
const ll mod = 998244353;
ll dp[maxn][maxn];

ll bin(ll x, ll n, ll MOD)
{
   ll ret = MOD != 1;
   for (x %= MOD; n; n >>= 1, x = x * x % MOD)
       if (n & 1)
           ret = ret * x % MOD;
   return ret;
}
inline ll get_inv(ll x, ll p) { return bin(x, p - 2, p); }

ll invf[maxn], fac[maxn] = {1};
void fac_inv_init(ll n, ll p)
{
   FOR(i, 1, n)
   fac[i] = i * fac[i - 1] % p;
   invf[n - 1] = bin(fac[n - 1], p - 2, p);
   FORD(i, n - 2, -1)
   invf[i] = invf[i + 1] * (i + 1) % p;
}

inline ll C(ll n, ll m)
{ // n >= m >= 0
   return n < m || m < 0 ? 0 : fac[n] * invf[m] % mod * invf[n - m] % mod;
}

int main()
{
   fac_inv_init(maxn, mod);
   ios::sync_with_stdio(false);
   int round;
   cin >> round;
   while (round--)
   {
       int n, m;
       cin >> n >> m;
       cin >> (s + 1) >> (t + 1);
       ll ans = 0;
       for (int i = 1; i <= n; i++)
       {
           if (s[i] != '0')
           {
               for (int j = m; j <= n - i; j++)
               {
                   ans = (ans + C(n - i, j)) % mod;
               }
           }
       }
       for (int i = 0; i <= n + 1; i++)
       {
           for (int j = 0; j <= m + 1; j++)
           {
               dp[i][j] = 0;
           }
       }

       for (int i = n; i >= 1; i--)
       {
           for (int j = m; j >= 1; j--)
           {
               if (s[i] == t[j])
               {
                   dp[i][j] = 
                     (dp[i + 1][j] + dp[i + 1][j + 1]) % mod;
               }
               else if (s[i] > t[j])
               {
                   dp[i][j] = 
                     (dp[i + 1][j] + C(n - i, m - j)) % mod;
               }
               else
               {
                   dp[i][j] = dp[i + 1][j];
               }
           }
       }
       cout << (dp[1][1] + ans) % mod << endl;
   }
}

预处理组合数的部分来自 ECNU 退役队伍 F0RE1GNERS 的模板 https://github.com/zerolfx/template