1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const i64 MOD = 998244353LL;

int n, k;
vector<i64> dp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    dp.assign(k + 1, 0);
    dp[0] = 1;

    // 直接按题意做 DP：
    // dp[j] = 处理完前若干个格子，恰好填了 j 个格子的方案数
    //
    // 处理第 i 个格子时：
    // 1. 不填，方案数不变
    // 2. 填一个数。若之前已经填了 j-1 个互不相同的数，
    //    那么 1..i 中还剩 i-(j-1) = i-j+1 个数可选。
    for (int i = 1; i <= n - 1; i++) {
        for (int j = min(i, k); j >= 1; j--) {
            dp[j] = (dp[j] + 1LL * (i - j + 1) * dp[j - 1]) % MOD;
        }
    }

    cout << dp[k] << '\n';

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int MAXN = 1000000 + 5;
const i64 MOD = 998244353LL;

int n, k;
int group_cnt;
i64 fact[MAXN], inv_fact[MAXN];

i64 quick_pow(i64 base, int exp) {
    i64 ans = 1;
    base %= MOD;

    while (exp > 0) {
        if (exp & 1) {
            ans = ans * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1;
    }

    return ans;
}

void init_comb(int up) {
    fact[0] = 1;
    for (int i = 1; i <= up; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    inv_fact[up] = quick_pow(fact[up], (int)MOD - 2);
    for (int i = up; i >= 1; i--) {
        inv_fact[i - 1] = inv_fact[i] * i % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    group_cnt = n - k;

    init_comb(group_cnt);

    // 原题答案 = 第二类 Stirling 数 S(n, n-k)
    // 用满射计数的容斥公式：
    // S(n,m) = 1 / m! * sum_{i=0}^{m} (-1)^i C(m,i) (m-i)^n
    //        = sum_{i=0}^{m} (-1)^i (m-i)^n / (i! (m-i)!)
    i64 ans = 0;
    for (int i = 0; i <= group_cnt; i++) {
        int remain = group_cnt - i;
        i64 term = quick_pow(remain, n);
        term = term * inv_fact[i] % MOD * inv_fact[remain] % MOD;

        if (i & 1) {
            ans -= term;
            if (ans < 0) {
                ans += MOD;
            }
        }
        else {
            ans += term;
            if (ans >= MOD) {
                ans -= MOD;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}