自动搬运

查看原文

来自洛谷，原作者为

	SunsetLake 说过要一起看的海 现在我独自等待

搬运于2025-08-24 22:52:09，当前版本为作者最后更新于2024-09-03 21:32:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

注意到题目中的限制条件是 $a_i >$ 一坨东西的 $\min$，那么可以从 $a_i$ 的最小值入手。因为没有比 $1$ 更小的了，所以 $1$ 一定要填在 $[1,k]$ 这个区间，才能保证序列的合法。

于是考虑 $1$ 的位置，设它在 $x$。那么对于 $[1,x)$ 就可以没有限制随便填，方案数就是 $C_{n - 1}^{x - 1}\times (x - 1)!$。对于 $(x,n]$ 的前 $k$ 个位置，你会发现没有限制了！因为最小的 $1$ 已经被填在了 $x$，不会有比它更小的数了。于是这部分的方案数转化成了一个新的子问题，记其为 $f_{n - x}$。故总方案数 $f_n = \displaystyle\sum\limits_{x = 1}^{\min(n,k)}C_{n - 1}^{x - 1}\times (x - 1)! \times f_{n - x}$，相当于做一个 dp 就行了。

但是直接求是 $O(nk)$ 的，需要优化一下。把 $C_{n - 1}^{x - 1}$ 写成 $\dfrac{(n - 1) !}{(x - 1)! \times (n - x)!}$，$(x - 1)!$ 就被消掉了，再将 $(n - 1)!$ 提到 $\sum$ 外面，得到：$f_n = (n - 1)!\displaystyle\sum\limits_{x = 1}^{\min(n,k)}\dfrac{f_{n - x}}{(n - x)!}$。这玩意儿用个前缀和维护就行了。

复杂度 $O(n)$。

code

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N = 1e7 + 5,mod = 998244353;
int n,k;
ll f[N],sum[N],fac[N],inv[N];
ll qpow(ll x,ll y){
	ll res = 1;
	while(y){
		if(y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
ll C(ll x,ll y){
	if(x < y || x < 0 || y < 0) return 0;
	return fac[x] * inv[y] % mod * inv[x - y] % mod;
}
int main(){
	cin >> n >> k;
	fac[0] = inv[0] = 1;
	for(int i = 1;i <= n;++ i) fac[i] = fac[i - 1] * i % mod;
	inv[n] = qpow(fac[n],mod - 2);
	for(int i = n - 1;i >= 1;-- i) inv[i] = inv[i + 1] * (i + 1) % mod;
	f[0] = sum[0] = 1;
	for(int i = 1;i <= n;++ i){
		f[i] = sum[i - 1];
		if(i - 1 - k >= 0) f[i] = (f[i] - sum[i - k - 1] + mod) % mod;
		f[i] = f[i] * fac[i - 1] % mod;
		sum[i] = (sum[i - 1] + f[i] * inv[i] % mod) % mod;
	}
	cout << f[n];
	return 0;
}