跳转至

CSP-S2025

卡常挂了 40pts，场上代码在洛谷（2s 时限）上跑就都没挂分。

T1

先不管 \(n/2\) 的限制贪心搞出一组方案，如果已经合法就直接输出，否则把超限的那一组贪心的分配到另外两组中。

100pts

T2

注意到只有原图的 mst 中的 \(n-1\) 条边可能有用，因此只保留它们即可。时间复杂度 \(O(nk2^k)\)。

并查集没写启发式合并被卡常变成 80pts。

T3

先找到 \(t_1\) 和 \(t_2\) 最前和最后不同的两个位置 \(mn,mx\)，然后把 \(t_1,t_2\) 同时放到 AC 机上跑，用 fail 树上的 dfn 序刻画匹配关系。发现这样做会把没有覆盖 \(mn\) 的匹配也算进去，因此从 \(mn+1\) 开始再跑一遍减掉即可。

因为 \(\log\) 在 \(L\) 上，因此被卡常 80pts，至今不知道怎么卡下 1s。

讲讲正常做法：把 \(s_1,s_2\) 最前和最后两个不同的位置也都拿出来，中间这一段必须和 \(t\) 的中间一段完全相等才可能产生贡献。因此对中间的一段进行哈希，两边的限制用字典树即可。这玩意的 \(\log\) 是带在 \(n\) 上的。

T4

场上只会 20pts 暴力。

设 \(f_{i,j,k}\) 表示考虑了前 \(i\) 天，有 \(j\) 个人没有录用，\(i\) 个人中有 \(k\) 个耐心大于 \(j\)，对应的方案数。转移考虑新来的人耐心是否大于 \(j\)，在 \(j++\) 的时候再钦定原先的 \(k\) 个人中有哪几个耐心是等于 \(j+1\) 的。

代码 
 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
#include<iostream>
#define int unsigned long long
using namespace std;
const int N = 510;
const int MOD = 998244353;

inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }

int n, m, ans;
int a[N], s[N], c[N];
int f[2][N][N];
int inv[N], fact[N], ifact[N];

inline int C(int a, int b) { return fact[a] * ifact[a - b] % MOD * ifact[b] % MOD; }
inline int A(int a, int b) { return fact[a] * ifact[a - b] % MOD; }

signed main() {

    inv[1] = fact[0] = ifact[0] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    for(int i = 1; i < N; i++) ifact[i] = ifact[i - 1] * inv[i] % MOD;

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        char c; cin >> c;
        a[i] = c == '1';
    }
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        c[x]++;
    }   
    s[0] = c[0];
    for(int i = 1; i <= n; i++) s[i] = s[i - 1] + c[i];

    f[0][0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= i; j++) {
            for(int k = 0; k <= i; k++) f[i & 1][j][k] = 0;
        }
        int t = (i & 1) ^ 1;
        if(a[i]) {
            for(int j = 0; j < i; j++) {
                for(int k = 0; k < i; k++)
                    add(f[i & 1][j][k + 1], f[t][j][k]);
                for(int k = max(0, (signed)i - (signed)s[j]); k < i; k++)
                    for(int l = 0, mx = min(k, c[j + 1]), tmp = s[j] - i + k + 1; l <= mx; l++)
                        add(f[i & 1][j + 1][k - l], f[t][j][k] * C(c[j + 1], l) % MOD * A(k, l) % MOD * tmp % MOD);
            }
        } else {
            for(int j = 0; j < i; j++) {
                for(int k = 0; k < i; k++)
                    for(int l = 0, mx = min(k + 1, c[j + 1]); l <= mx; l++)
                        add(f[i & 1][j + 1][k - l + 1], f[t][j][k] * C(c[j + 1], l) % MOD * A(k + 1, l) % MOD);
                for(int k = max(0, (signed)i - (signed)s[j]); k < i; k++)
                    for(int l = 0, mx = min(k, c[j + 1]), tmp = s[j] - i + k + 1; l <= mx; l++)
                        add(f[i & 1][j + 1][k - l], f[t][j][k] * C(c[j + 1], l) % MOD * A(k, l) % MOD * tmp % MOD);
            }
        }
    }

    for(int j = 0; j <= n - m; j++) {
        for(int k = 0; k <= n - s[j]; k++) {
            add(ans, f[n & 1][j][k] * fact[k] % MOD);
        }
    }
    cout << ans << '\n';

    return 0;
}