题解：P6162 [Cnoi2020] 四角链

szh_AK_all · 2024-07-13 19:38:27 · 题解

分析

不妨先设 f_{i,j} 表示前 i 个格子中有 j 个格子填了数的方案数，那么第 i 个格子可以放数，也可以不放，对应的转移方程便是 f_{i,j}=(i-j-1)\times f_{i-1,j-1}+f_{i-1,j}，可以发现这个和第二类斯特林数很像，那么如何让把个式子转换为第二类斯特林数呢？

第二类斯特林数的式子是 S_{n,r}=r\times S_{n-1,r}+S_{n-1,r-1}，可以发现第二类斯特林数的式子与上述的转移方程隔在了哪里呢？显然，最特别的是 i-j-1,r 这两个相对应的系数，可以尝试改变 f_{i,j} 的含义。

设 f_{i,j} 表示前 i 个格子中有 j 个格子没填数的方案数，那么转移方程便为 f_{i,j}=j\times f_{i-1,j}+f_{i-1,j-1}，可以发现，这和第二类斯特林数便相同了，最终答案即为 f_{n-1,n-k}，用通项公式求下即可（在代码里，f_{i,j} 的含义如上文所述略有不同）。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int mod = 998244353;
int jie[1000005], inv[1000005];

int qpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b % 2 == 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return ans;
}

int c(int n, int m) {
    return jie[n] * inv[m] % mod * inv[n - m] % mod;
}

signed main() {
    int n, k;
    cin >> n >> k;
    jie[0] = 1;
    inv[0] = qpow(1, mod - 2);
    for (int i = 1; i <= n; i++)
        jie[i] = jie[i - 1] * i % mod, inv[i] = qpow(jie[i], mod - 2);
    int ans = 0;
    for (int i = 0; i <= n - k - 1; i++) {
        int f = 1;
        if (i % 2 == 1)
            f = -1;
        ans += f * c(n - k, i) % mod * qpow(n - k - i, n) % mod;
        if (ans > mod)
            ans -= mod;
        if (ans < 0)
            ans += mod;
    }
    ans = ans * inv[n - k] % mod;
    cout << ans;
}