题解：P6162 [Cnoi2020] 四角链

传送门

绝大多数的计数题都可以用 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}\)。那么有状态转移方程：

\[f_{i,j}=f_{i-1,j}+(i-j+1)\times f_{i-1,j-1} \]

我们先把 \(i,j\) 用题目中的 \(n,k\) 替换一下，得到：

\[f_{n,k}=f_{n-1,k}+(n-k+1)\times f_{n-1,k-1} \]

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

\[f_{n,n-k+1}=f_{n-1,n-k+1}+k\times f_{n-1,n-k} \]

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

\[S_{n,k}=S_{n-1,k-1}+k\times S_{n-1,k} \]

这就是第二类 Stirling 数的递推式，因此答案是 \(\begin{Bmatrix}n\\n-k\end{Bmatrix}\)，直接用通项公式计算即可：

\[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^m\frac{(-1)^i(m-i)^n}{i!(m-i)!}\Rightarrow\begin{Bmatrix}n\\{n-k}\end{Bmatrix}=\sum_{i=0}^{n-k}\frac{(-1)^i(n-k-i)^n}{i!(n-k-i)!} \]

我们还可以用另一种方法推导出本题的答案，考虑下面关于 \(n=6,k=3\) 的填数方案（第一行代表位置，第二行代表所填的数，不填的位置假设填 \(0\)）：

\(1\)	\(2\)	\(3\)	\(4\)	\(5\)
\(0\)	\(1\)	\(2\)	\(0\)	\(4\)

我们给这个数表加一个表头，再在 \(i=1\) 的列前面加一个 \(i=0\) 的列（因为原题中 \(n\) 这个数对答案不产生贡献，所以这里其实是把多出来的那个 \(n\) 等价替换成数表最前面的 \(0\)）：

\(i\)	\(0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)
\(fa_i\)	\(0\)	\(0\)	\(1\)	\(2\)	\(0\)	\(4\)

注意到按该表连边之后形成的图是一棵以 \(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;
}