自动搬运

查看原文

来自洛谷，原作者为

	ztd___ 时代的眼泪。

搬运于2025-08-24 23:08:51，当前版本为作者最后更新于2025-01-26 13:48:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

你点开了题目。

题目中的“方案数对 $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;
}

你发现自己还是太菜了。