传送门
绝大多数的计数题都可以用 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\)):
\(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;
}