2025牛客暑期多校训练营7

时间和 xcpc 系统测试赛撞了，所以是周五 vp 的，大概情况是这样的

STATUS	COUNT
AC	5
赛后补	1

vp 排名 185，这场打的比较好，最后 I 题差点就调出来了，结束后 3min 一发 A 了，如果当时过了了 I 题排名就 98 了。

A. Loopy Laggon ^队友#

Alice 的旋转不会改变逆序数，外环是一个 12-轮换，内环是一个 4-轮换，可以拆成 11 + 3 = 14 个对换，不改变逆序数奇偶性，Bob 随机放置只有 $\frac{1}{2}$ 的概率放对，一套 10 个检查出来的概率是 $1 - \frac{1}{2^{10}}$ ，可以答对 90%，他没卡暴力求逆序数的方法。

讲题的时候讲了一种 O(n) 判断排列奇偶性的方法，从左往右扫一遍如果有一个数不在他的位置上就换回来，奇偶性取反，直到换完，裸的板子大概是这样的，也记录一下。

1
#include <iostream>
2

3
using namespace std;
4

5
int a[10], p[10];
6

7
int main() {
8
    int n;
9
    scanf("%d", &n);
10
    for (int i = 0; i < n; ++i) {
11
        scanf("%d", &a[i]);
12
        p[a[i]] = i;
13
    }
14
    int f = 0;
15
    for (int i = 0; i < n; ++i) {
16
        if (a[i] != i + 1) {
17
            swap(a[i], a[p[i + 1]]);
18
            swap(p[a[i]], p[a[p[i + 1]]]);
19
            f ^= 1;
20
        }
21
    }
22
    return 0;
23
}

这是这道题的 AC 代码

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 100;
6
int a[N], p[N];
7

8
int main() {
9
    int id, m, k, n, l;
10
    scanf("%d%d%d%d", &id, &m, &k, &n);
11
    l = n * n;
12
    while (m--) {
13
        bool f = false;
14
        for (int t = 0; t < k; ++t) {
15
            int cnt = 0;
16
            for (int i = 0; i < l; ++i) {
17
                scanf("%d", &a[i]);
18
                p[a[i]] = i;
19
            }
20
            for (int i = 0; i < l; ++i) {
21
                if (a[i] != i + 1) {
22
                    swap(a[i], a[p[i + 1]]);
23
                    swap(p[a[i]], p[a[p[i + 1]]]);
24
                    cnt ^= 1;
25
                }
26
            }
27
            if (cnt & 1) f = true;
28
        }
29
        printf(f ? "1" : "0");
30
    }
31
    printf("\n");
32
    return 0;
33
}

F. Forsaken City ^队友#

一道签到题，枚举 i，答案是 $\max_{1 \le i \le n} \max_{1 \le j < i} - a_i$ .

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 200010;
6
int a[N];
7

8
int main() {
9
    int T;
10
    scanf("%d", &T);
11
    while (T--) {
12
        int n, res = 0, mx = 0;
13
        scanf("%d", &n);
14
        for (int i = 1; i <= n; ++i) {
15
            scanf("%d", &a[i]);
16
            if (i > 1) res = max(res, mx - a[i]);
17
            mx = max(mx, a[i]);
18
        }
19
        printf("%d\n", res);
20
    }
21
    return 0;
22
}

F. The Correlation#

这道题是我写的，而且我是战犯😭

贪心的想，每次取最大最小值一半都能最大程度减少 $\sum_{1 \le i < j \le n} \left|a_i - a_j\right|$ ，但是我写的时候写了个 (mx - mn) / 2，还得全队吃 2 发罚时，这事可能不完全怪我，但是我确实没想清，旁边说一嘴我就信了……我逃不了主要责任

1
#include <iostream>
2
#include <algorithm>
3
#include <climits>
4

5
using namespace std;
6

7
typedef long long LL;
8
const int N = 200010;
9
const int MOD = 998244353;
10
LL a[N];
11

12
int main() {
13
    int n;
14
    scanf("%d", &n);
15
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
16
    LL res = LLONG_MAX;
17
    for (int t = 0; t < n; ++t) {
18
        LL mn = LLONG_MAX, mx = LLONG_MIN;
19
        for (int i = 1; i <= n; ++i) {
20
            mn = min(a[i], mn), mx = max(a[i], mx);
21
        }
22
        int v = (mx + mn) / 2;
23
        LL pre_s = 0, cur_res = 0;
24
        for (int i = 1; i <= n; ++i) a[i] = abs(a[i] - v);
25
        sort(a + 1, a + n + 1);
26
        for (int i = 1; i <= n; ++i) {
27
            cur_res = ((cur_res + (LL)a[i] * (i - 1) % MOD - pre_s) % MOD + MOD) % MOD;
28
            pre_s = (pre_s + a[i]) % MOD;
29
        }
30
        res = cur_res;
31
        bool f = true;
32
        for (int i = 1; i <= n; ++i) {
33
            if (a[i] != 0 && a[i] != 1) {
34
                f = false;
35
                break;
36
            }
37
        }
38
        if (f) break;
39
    }
40
    printf("%lld\n", res);
41
    return 0;
42
}

G. Nice Doppelgnger#

这题一发过了，某种意义上算是当天把欠的补了吧，最近这是第二个用线筛 dp 的题了，吸取上次写挂的教训，这次一遍就对了。

刚开始还打算打表来着，但是突然注意~~(猜)~~到一个关键性质，如果一个数的幂次为奇数的质因数个数为奇数个，加入集合一定不会和其他两个数组成平方数，队友考虑到有这个性质的数正好一定至少有一半（只考虑 2 的幂次，如果一个数不满足那么他的 2 倍一定满足），遂大胆的写。

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5
const int N = 1000010;
6
int prime[N], v[N];
7
bool f[N];
8

9
int main() {
10
    int m = 1000000, l = 0;
11
    for (int i = 2; i <= m; ++i) {
12
        if (v[i] == 0) {
13
            v[i] = i;
14
            prime[++l] = i;
15
            f[i] = true;
16
        }
17
        for (int j = 1; j <= l; ++j) {
18
            if (prime[j] > v[i] || prime[j] > m / i) break;
19
            v[i * prime[j]] = prime[j];
20
            f[i * prime[j]] = f[i] ^ 1;
21
        }
22
    }
23
    int T;
24
    scanf("%d", &T);
25
    while (T--) {
26
        int n;
27
        scanf("%d", &n);
28
        int lim = n / 2;
29
        for (int i = 2; i <= n; ++i) {
30
            if (f[i]) {
31
                printf("%d ", i);
32
                lim--;
33
                if (lim == 0) break;
34
            }
35
        }
36
        printf("\n");
37
    }
38
    return 0;
39
}

I. Lava Layer ^补#

大型矩阵快速幂加速期望 dp，太恶心了，写的有一种大模拟即视感，最后结束后三分钟队友成功调出来了……

这是期间我写的线性 dp 代码最终版，先调对状态转移方程然后给矩阵对照，大寄了差不多三次

位运算逻辑写错，按位或和按位异或不能直接对那个期望值算，应该用后四位和当前数码运算一下加上这个 delta 值 * 概率；
大逻辑有问题，除了乘法外的 delta 值要乘上过来的概率，我之前没乘，趁着别人写 A 的时候手算了一个样例验证了新结论正确；
还是位运算写错，按位与不是相加而是直接赋值成 (后四位 & 当前数码) * 概率，因为前面的全与掉了。

1
#include <iostream>
2
#include <vector>
3
#include <cstring>
4

5
using namespace std;
6
typedef long long LL;
7
const int N = 1000010;
8
const int MOD = 998244353;
9

10
LL power(LL n, LL p) {
11
    LL res = 1, base = n;
12
    while (p) {
13
        if (p & 1) res = res * base % MOD;
14
        base = base * base % MOD;
15
        p >>= 1;
16
    }
17
    return res;
18
}
19
LL f[N][1 << 4], g[N][1 << 4];
20
vector<LL> s;
21

22
int main() {
23
    LL inv5 = power(5, MOD - 2);
24
    int T;
25
    scanf("%d", &T);
26
    while (T--) {
27
        LL n;
28
        int k;
29
        scanf("%lld%d", &n, &k);
30
        s.clear();
31
        s.resize(k);
32
        for (int i = 0; i < k; ++i) {
33
            scanf("%lld", &s[i]);
34
        }
35
        memset(f, 0, sizeof(f));
36
        memset(g, 0, sizeof(g));
37
        LL invk = power(k, MOD - 2);
38
        for (int i : s) {
39
            f[0][i & 15] = invk * i % MOD;
40
            g[0][i & 15] = invk;
41
        }
42
        for (int i = 1; i < n; ++i) {
43
            for (LL msk = 0; msk < (1 << 4); ++msk) {
44
                for (int j : s) {
45
                    g[i][(j + msk) & 15] = (g[i][(j + msk) & 15] + g[i - 1][msk] * inv5 % MOD * invk % MOD) % MOD;
46
                    g[i][(j * msk) & 15] = (g[i][(j * msk) & 15] + g[i - 1][msk] * inv5 % MOD * invk % MOD) % MOD;
47
                    g[i][(j & msk) & 15] = (g[i][(j & msk) & 15] + g[i - 1][msk] * inv5 % MOD * invk % MOD) % MOD;
48
                    g[i][(j | msk) & 15] = (g[i][(j | msk) & 15] + g[i - 1][msk] * inv5 % MOD * invk % MOD) % MOD;
49
                    g[i][(j ^ msk) & 15] = (g[i][(j ^ msk) & 15] + g[i - 1][msk] * inv5 % MOD * invk % MOD) % MOD;
50

51
                    f[i][(j + msk) & 15] = (f[i][(j + msk) & 15] + (f[i - 1][msk] + g[i - 1][msk] * j) % MOD * inv5 % MOD * invk % MOD) % MOD;
52
                    f[i][(j * msk) & 15] = (f[i][(j * msk) & 15] + (f[i - 1][msk] * j) % MOD * inv5 % MOD * invk % MOD) % MOD;
53
                    f[i][(j & msk) & 15] = (f[i][(j & msk) & 15] + ( g[i - 1][msk] * ((LL)(msk & j))) % MOD * inv5 % MOD * invk % MOD) % MOD;
54
                    f[i][(j | msk) & 15] = (f[i][(j | msk) & 15] + (f[i - 1][msk] + g[i - 1][msk] * ((LL)(msk | j) - msk + MOD)) % MOD * inv5 % MOD * invk % MOD) % MOD;
55
                    f[i][(j ^ msk) & 15] = (f[i][(j ^ msk) & 15] + (f[i - 1][msk] + g[i - 1][msk] * ((LL)(msk ^ j) - msk + MOD)) % MOD * inv5 % MOD * invk % MOD) % MOD;
56
                }
57
            }
58
            // for (int msk = 0; msk < (1 << 4); ++msk) {
59
            //     cout << f[i][msk] << ' ';
60
            // }
61
            // cout << endl;
62
        }
63
        LL res = 0;
64
        for (int i = 0; i < (1 << 4); ++i) {
65
            res = (res + f[n - 1][i]) % MOD;
66
        }
67
        printf("%lld\n", res);
68
    }
69
    return 0;
70
}

然后转化成向量和矩阵的形式，初始状态一个行向量 $\begin{pmatrix} f_0 & g_0 \end{pmatrix}$ 拼到一起，状态转移方程写成一个矩阵，行号 -> 列号是一次转移初状态到末状态的贡献倍率，没有这一项就填 0.

后来我偷学了队友怎么开的数组，也自己重写了一版，没有当时的紧张感倒是调的快多了，几乎没出什么问题就过去了。

1
#include <iostream>
2
#include <vector>
3
#include <cstring>
4

5
using namespace std;
6
typedef long long LL;
7
const int MOD = 998244353;
8
const int N = 32;
9

10
LL power(LL n, LL p) {
11
    LL res = 1, base = n;
12
    while (p) {
13
        if (p & 1) res = res * base % MOD;
14
        base = base * base % MOD;
15
        p >>= 1;
16
    }
17
    return res;
18
}
19

20
LL f[N], g[N], a[N][N], b[N][N];
21
vector<LL> s;
22

23
void mul1() {
24
    memset(g, 0, sizeof(g));
25
    for (int i = 0; i < N; ++i) {
26
        for (int j = 0; j < N; ++j) {
27
            g[i] = (g[i] + a[j][i] * f[j]) % MOD;
28
        }
29
    }
30
    memcpy(f, g, sizeof(f));
31
}
32

33
void mul2() {
34
    memset(b, 0, sizeof(b));
35
    for (int k = 0; k < N; ++k) {
36
        for (int i = 0; i < N; ++i) {
37
            for (int j = 0; j < N; ++j) {
38
                b[i][j] = (b[i][j] + a[i][k] * a[k][j]) % MOD;
39
            }
40
        }
41
    }
42
    memcpy(a, b, sizeof(a));
43
}
44

45
int main() {
46
    LL inv5 = power(5, MOD - 2);
47
    int T;
48
    scanf("%d", &T);
49
    while (T--) {
50
        LL n;
51
        int k;
52
        scanf("%lld%d", &n, &k);
53
        LL invk = power(k, MOD - 2), inv5k = invk * inv5 % MOD;
54
        memset(f, 0, sizeof(f));
55
        memset(a, 0, sizeof(a));
56
        s.resize(k);
57
        for (LL& i : s) {
58
            scanf("%d", &i);
59
            f[i] = invk * i % MOD;
60
            f[i + 16] = invk;
61
        }
62
        for (int msk = 0; msk < 16; ++msk) {
63
            for (LL& i : s) {
64
                // +
65
                a[msk][(msk + i) & 15] = (a[msk][(msk + i) & 15] + inv5k) % MOD;
66
                a[msk + 16][(msk + i) & 15] = (a[msk + 16][(msk + i) & 15] + i * inv5k) % MOD;
67
                a[msk + 16][((msk + i) & 15) + 16] = (a[msk + 16][((msk + i) & 15) + 16] + inv5k) % MOD;
68
                // *
69
                a[msk][(msk * i) & 15] = (a[msk][(msk * i) & 15] + i * inv5k) % MOD;
70
                a[msk + 16][((msk * i) & 15) + 16] = (a[msk + 16][((msk * i) & 15) + 16] + inv5k) % MOD;
71
                // &
72
                a[msk + 16][(msk & i) & 15] = (a[msk + 16][(msk & i) & 15] + (msk & i) * inv5k) % MOD;
73
                a[msk + 16][((msk & i) & 15) + 16] = (a[msk + 16][((msk & i) & 15) + 16] + inv5k) % MOD;
74
                // |
75
                a[msk][(msk | i) & 15] = (a[msk][(msk | i) & 15] + inv5k) % MOD;
76
                a[msk + 16][(msk | i) & 15] = (a[msk + 16][(msk | i) & 15] + ((i | msk) - msk + MOD) * inv5k) % MOD;
77
                a[msk + 16][((msk | i) & 15) + 16] = (a[msk + 16][((msk | i) & 15) + 16] + inv5k) % MOD;
78
                // ^
79
                a[msk][(msk ^ i) & 15] = (a[msk][(msk ^ i) & 15] + inv5k) % MOD;
80
                a[msk + 16][(msk ^ i) & 15] = (a[msk + 16][(msk ^ i) & 15] + ((i ^ msk) - msk + MOD) * inv5k) % MOD;
81
                a[msk + 16][((msk ^ i) & 15) + 16] = (a[msk + 16][((msk ^ i) & 15) + 16] + inv5k) % MOD;
82
            }
83
        }
84
        n--;
85
        while (n) {
86
            if (n & 1) mul1();
87
            mul2();
88
            n >>= 1;
89
        }
90
        LL res = 0;
91
        for (int i = 0; i < (1 << 4); ++i) {
92
            res = (res + f[i]) % MOD;
93
        }
94
        printf("%lld\n", res);
95
    }
96
    return 0;
97
}

J. Ivory ^队友#

巧妙的数学题，不断取 b 和 d 中较小的消较大的，利用残余部分互质，留出一个常数提到外面继续递归。

1
#include <iostream>
2

3
using namespace std;
4
typedef long long LL;
5
const int MOD = 998244353;
6

7
LL power(LL n, LL p) {
8
    n %= MOD;
9
    LL res = 1, base = n;
10
    while (p) {
11
        if (p & 1) res = res * base % MOD;
12
        base = base * base % MOD;
13
        p >>= 1;
14
    }
15
    return res;
16
}
17

18
LL gcd(LL a, LL b) {
19
    return b ? gcd(b, a % b) : a;
20
}
21

22
LL work(LL a, LL b, LL c, LL d) {
23
    if (a == 1 || c == 1) return 1;
24
    if (b > d) swap(a, c), swap(b, d);
25
    LL g = gcd(a, c);
26
    return power(g, b) * work(a / g, b, g, d - b) % MOD;
27
}
28

29
int main() {
30
    int T;
31
    scanf("%d", &T);
32
    while (T--) {
33
        LL a, b, c, d;
34
        scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
35
        printf("%lld\n", work(a, b, c, d));
36
    }
37
    return 0;
38
}

Star's Blog

A. Loopy Laggon 队友#

F. Forsaken City 队友#