$$
f_i = \max(f_{i-m}+\frac{c!}{m^m},f_{i-1})
$$
可以对 $f$ 乘上 $m^m$ 最后再除掉。
由于要比较大小，所以要存储精确值，把每个数表示成阶乘：
$$
x=\sum_{j\ge1}d_j\,j!,\qquad 0\le d_j\le j
$$
对于这种进制，比较大小可以直接从高往低比较，加法就按位模拟。
容易发现 $f_i$ 只有最多 $O(m+\log n)$ 位，若直接存储转移，复杂度是 $O(nm)$ 的。还有一种存储方式是存所有非零位的值，非零位最多只有 $\frac{n}{m}$ 个，时间复杂度为 $O(\frac{n^2}{m})$。
根号分治一下，时间复杂度为 $O(n \sqrt{n})$。但是空间爆了。注意到 $f$ 只要保留最新的 $m$ 个即可，空间复杂度 $O(n)$。可以通过。
## 代码
::::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int n, m, w;
bool fl;
vector<vector<int> > f;
vector<int> g, len;
inline int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod, b >>= 1;
}
return res;
}
inline void add1(int p) {
g[p] ++;
while (g[p] > p) {
g[p] = 0;
p ++;
g[p] ++;
}
}
inline void add2(int p, int &s) {
int l = 1;
while (l <= s && g[l] < p) l ++;
int r = l;
while (r + p - 1 <= s && g[r + p - 1] == p) {
r += p;
p ++;
}
if (l == r)
for (int i = s; i >= l; i --) g[i + 1] = g[i];
else
for (int i = r; i <= s; i ++) g[i + 1 - r + l] = g[i];
g[l] = p;
s = s - (r - l) + 1;
}
inline bool chk(int s, int v) {
int t = len[v];
while (s && t) {
if (g[s] != f[v][t]) return g[s] > f[v][t];
s --, t --;
}
return s > t;
}
signed main() {
ios :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
int k = n / m, h = m + 1;
if (k == 1) {
vector<int> a(n + 1), cnt(m + 1);
int z = 0, bad = 0, mx = -1;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
if (!a[i]) z ++;
else if (++ cnt[a[i]] == 2) bad ++;
if (i > m) {
int x = a[i - m];
if (!x) z --;
else if (cnt[x] -- == 2) bad --;
}
if (i >= m && !bad) mx = max(mx, z);
}
int ans = (mx >= 0);
for (int i = 2; i <= mx; i ++) ans = 1ll * ans * i % mod;
cout << 1ll * ans * qpow(qpow(m, m), mod - 2) % mod << '\n';
return 0;
}
for (int t = k; t > 1; t >>= 1) h ++;
fl = m <= k;
w = fl ? h : k;
f.assign(m, vector<int> (w + 1));
g.resize(w + 1);
len.assign(m, fl ? w : 0);
vector<int> a(n + 1), cnt(m + 1), fac(h + 1);
fac[0] = 1;
for (int i = 1; i <= h; i ++) fac[i] = 1ll * fac[i - 1] * i % mod;
int z = 0, bad = 0;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
if (a[i] == 0) z ++;
else if (++ cnt[a[i]] == 2) bad ++;
if (i > m) {
int x = a[i - m];
if (x == 0) z --;
else if (cnt[x] -- == 2) bad --;
}
if (i < m) continue;
int u = i % m, v = (i - 1) % m;
int s = len[u];
bool t = 0;
if (bad == 0) {
for (int j = 1; j <= s; j ++) g[j] = f[u][j];
int p = max(z, 1);
if (fl) add1(p);
else add2(p, s);
t = chk(s, v);
}
if (t) {
len[u] = s;
for (int j = 1; j <= s; j ++) f[u][j] = g[j];
} else {
len[u] = len[v];
for (int j = 1; j <= len[v]; j ++) f[u][j] = f[v][j];
}
}
int u = n % m;
long long ans = 0;
for (int j = 1; j <= len[u]; j ++) {
if (fl) ans += 1ll * f[u][j] * fac[j];
else ans += fac[f[u][j]];
}
cout << ans % mod * qpow(qpow(m, m), mod - 2) % mod;
return 0;
}
::::