傳送門

絕大多數的計數題都可以用 dp 和容斥解決。

本題的 dp 比較好想，設 \(f_{i,j}\) 表示前 \(i\) 個位置填了 \(j\) 個數。考慮如果第 \(i\) 個位置不填，則貢獻是 \(f_{i-1,j}\)；否則前面 \(i-1\) 個位置一共填了 \(j-1\) 個數，由于第 \(i\) 個位置可以填 \(1\sim i\)，則第 \(i\) 個位置有 \(i-j+1\) 種填的方法，貢獻是 \((i-j+1)f_{i-1,j-1}\)。那么有狀態轉移方程：

我們先把 \(i,j\) 用題目中的 \(n,k\) 替換一下，得到：

再用 \(n-k+1\) 代換掉 \(k\)，得到：

令 \(S_{n,k}=f_{n,n-k+1}\)，得到：

這就是第二類 Stirling 數的遞推式，因此答案是 \(\begin{Bmatrix}n\\n-k\end{Bmatrix}\)，直接用通項公式計算即可：

我們還可以用另一種方法推導出本題的答案，考慮下面關于 \(n=6,k=3\) 的填數方案（第一行代表位置，第二行代表所填的數，不填的位置假設填 \(0\)）：

我們給這個數表加一個表頭，再在 \(i=1\) 的列前面加一個 \(i=0\) 的列（因為原題中 \(n\) 這個數對答案不產生貢獻，所以這里其實是把多出來的那個 \(n\) 等價替換成數表最前面的 \(0\)）：

注意到按該表連邊之后形成的圖是一棵以 \(0\) 為根節點、根節點的 \(n-k-1\) 棵子樹形態均為鏈的樹。

證明：由于一共填 \(k\) 個數，也即有 \(n-k-1\) 個數沒有填，在該表中表現為填了 \(n-k-1\) 個 \(0\)，因此若以 \(0\) 為根節點，則根節點有 \(n-k-1\) 棵子樹。同時因為不允許填重復的數，所以除了根節點以外，其它節點最多只有一棵子樹，因此這些根節點的子樹形成了鏈狀結構。

那么現在問題等價轉化為：將 \(1\sim n-1\) 這 \(n\) 個數有祖孫關系地掛在 \(n-k-1\) 條鏈上的方案數。再等價轉化一步，即將 \(1\sim n-1\) 這 \(n-1\) 個數劃分為 \(n-k-1\) 個互不區分的非空子集方案數。再用 \(n\) 代換掉 \(n-1\)，即將 \(1\sim n\) 這 \(n\) 個數劃分為 \(n-k\) 個互不區分的非空子集方案數。

這就是第二類 Stirling 數的定義，因此答案為 \(\begin{Bmatrix}n\\n-k\end{Bmatrix}\)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353, N = 1e6 + 10;
int n, k;
int qpow (int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1)
			res = res * a % mod;
	return res;
}
int fac[N], inv[N];
void init () {
	fac[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; i; --i)
		inv[i - 1] = inv[i] * i % mod;
}
int S (int n, int m) {
	int res = 0;
	for (int i = 0; i <= m; ++i)
		res = (res + qpow(m - i, n) * inv[i] % mod * inv[m - i] % mod * ((i & 1) ? -1 : 1) + mod) % mod;
	return res;
}
signed main () {
	cin >> n >> k, init(), cout << S(n, n - k);
	return 0;
}