P11616 题解

· · 题解

你点开了题目。

题目中的“方案数对 998244353 取模的结果”，都无时无刻不在告诉你：这是道计数题。

但是你会不了一点计数。你只学过组合数和 DP，对其他内容一无所知。

你伤心透顶，却看见榜上过题的人数正在飞快增长，大家用行动提醒你：这题并不难。

看着 10^7 的数据范围，你认为这题正解一定是线性，而目前自己学过的线性计数算法只有 DP 了。你用你敏锐的目光发现了 n 和 m 两个字母。

“有 n 和 m，那大概率是 DP 了。”但是你忘了，组合数的标准形式就是 C_n^m。

思考正解无果，你决定思考部分分。思考部分分无果后， 你回想起之前自己做过的一些 DP 题目和有关套路，突发奇想，想到了该如何设计状态。

“部分分做法可以先不用在意复杂度吧，那完全可以用 dp_{i,j} 表示前 i 个数字分成 j 段的方案数啊！然后当 a_i \le a_{i-1} 时，必须单独分段，即 dp_{i,j} = dp_{i-1,j-1}，否则可以多分一段，即 dp_{i,j} = dp_{i-1,j}+dp_{i-1,j-1}，最后注意一下边界不就好了？”

你兴高采烈，写完代码提交上去，却只有可怜的 30pts。你汗流浃背了。你分析复杂度，发现是 O(nm)。那肯定过不了了啊。

你非常慌张，一直思考怎么将问题化为一维。思考无果。你以 30pts 的好成绩退下了比赛。

赛后，你观看了题解。

“哎哎哎不是，这怎么是组合数啊？？？”

你悲痛万分，为自己在 DP 上花费的 2h+ 而心如刀绞。

痛定思痛。你决定仔细研究一下这题。

你发现这题转化后就是典型的组合数。

将问题转化为从若干个间隔里选若干个间隔的方案，然后再去掉必须隔开的 a_i \le a_{i-1} 的情况（设其个数为 cnt），总间隔数就是 n - 1 - cnt，可选择的间隔数可以从 0 到 m - 1 - cnt 枚举，将答案相加即可。cnt 完全可以线性处理。

形式化地，就是求出：

\sum_{i=0}^{m-1-cnt} C_{n-1-cnt}^{i}

发现这题确实这么简单，你心中更难受了。

你决定先把框架写了。

void _solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int cnt = 0, ans = 0;
    for (int i = 2; i <= n; i++) {
        if (a[i] <= a[i - 1]) cnt++;
    }
    for (int i = 0; i <= m - cnt - 1; i++) {
        ans = (ans + C(n - 1 - cnt, i)) % MOD;
    }
    if (cnt > m - 1) cout << 0 << "\n";
    else cout << ans << "\n";
}

正当你准备写组合数部分时，你突然发现组合数没法算，用杨辉三角递推太慢了，只能用阶乘直接算。即：

C_n^m = \frac{n!}{(n-m)! \times m!}

阶乘可以线性预处理，但除法呢？众所周知，在模意义下不能直接算除法啊。

你想到了一个东西：乘法逆元。

仔细学习了若干小时后，你学会了线性递推求乘法逆元！

你开始写代码，然后又发现了问题：阶乘取模后可能还是很大，线性递推推不到那么大。

你仔细地推了一段公式，其中 inv_i 表示 i 在模 998244353 意义下的逆元：

\because i! = (i - 1)! \times i \therefore inv_{i!} = inv_{(i-1)! \times i}

根据同余易得：inv_{(i-1)! \times i} = inv_{(i-1)!} \times inv_{i}

所以 inv_{i!} = inv_{(i-1)!} \times inv_i

感觉推了跟没推一样啊！但是你发现这个结论确实不需要很难的推理，而且 1! = 1 没有变化，所以可以直接从 1 开始推。你决定开始写代码。

其中，你为了节省空间，决定用预处理过的 inv 数组直接处理 i! 的逆元。阶乘数组求组合数时需要用来表示分子 n!，但是逆元数组没有用处，所以可以直接在逆元数组 inv 上推。

你写出了预处理代码。

const int N = 1e7 + 77;
const int MOD = 998244353;
int inv[N], fac[N], n, m, a[N];
void _init() {
    inv[0] = inv[1] = fac[0] = fac[1] = 1;
    for (int i = 2; i <= 1e7; i++) {
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
        fac[i] = fac[i - 1] * i % MOD;
    }
    for (int i = 2; i <= 1e7; i++) {
        inv[i] = inv[i - 1] * inv[i] % MOD;
    }
}

然后你发现组合数的计算就一行，算上框架也才三行，所以把它写了出来。

int C(int n, int m) {
    return fac[n] * inv[n - m] % MOD * inv[m] % MOD;
}

然后你发现将上述代码块拼起来，加个 main 函数和头文件啥的就 AC 了。

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    _init();
    int T;
    cin >> T;
    while (T--) _solve();
    return 0;
}

你发现自己还是太菜了。