题目背景

众所周知，XG_Zepto 是一位来自 FZOI 的神仙。他觉得眼下的比赛太简单了，就用扫雷的时间出了一道数学题给 kal0rona。kal0rona 太菜了，看不懂题也不会写，之后求救于你了。

题目思路

很好的一道计数 DP，出自神仙组长 XG_Zepto 之手。首先，设\(f[i][j]\)为长度为\(i\)，换弹次数为\(j\)时满足条件的排列数量。之后，考虑枚举第\(i\)个数字出现的位置\(k\)，对于位置\(k\)后面的数字是不会有特殊贡献的（贡献为\((i-k)!\)），而对于前面的数，可以进行枚举前一段进行转移，一共有\({k-1}\choose{i-1}\)种选数字的方案和\(f[i-1][j-1\)种排列，乘起来即可，也就是：

\[ F[i][j] = \sum_{k = 1}^{i}f[k-1][j-1]* {{k-1} \choose {i-1}} *(i-1)! \]

可以化简，并用前缀和优化：

\[ F[i][j] = (i-1)!\sum_{k=1}^{i}\frac{f[k-1][j-1]}{(k-1)!} \]

代码

// U63113.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 5050, mod = 998244353;
ll f[MAX_N], prefix[MAX_N], level[MAX_N], inv[MAX_N], n, m;
ll quick_pow(ll bas, ll tim)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld", &n, &m);
    level[0] = 1, inv[0] = 1;
    for (int i = 1; i <= n; i++)
        level[i] = level[i - 1] * i % mod;
    inv[n] = quick_pow(level[n], mod - 2);
    for (int i = n; i >= 1; i--)
        inv[i - 1] = inv[i] * i % mod;
    for (int i = 0; i <= n; i++)
        prefix[i] = 1;
    for (int j = 1; j <= m; j++)
    {
        for (int i = j; i <= n; i++)
            f[i] = prefix[i - 1] * level[i - 1] % mod;
        for (int i = j; i <= n; i++)
            prefix[i] = f[i] * inv[i] % mod;
        for (int i = j + 1; i <= n; i++)
            prefix[i] = (prefix[i] + prefix[i - 1]) % mod;
    }
    printf("%lld", f[n]);
    return 0;
}