P10315 [SHUPC 2024] - 原神，启动！题解

Done

您已获得最佳的阅读体验！

本题考察模意义下的高斯消元。

基本思路是，让 ${1\sim n}$ 号方块分别击打 $x_1\sim x_n$ 次，使得最终每个方块都朝向位置 $t_1\sim t_n$ 。

欲解决此题，首先需要为每个位置编号。定义 $a\rightarrow b,c$ 为“击打 $a$ 方块后， $a,b,c$ 均会旋转一次”。那么样例输入 #1 如下图（编号方式不唯一），红线为目标方向、初始时均在 $0$ 朝向：

假设三个方块需要击打 $x,y,z$ 次，那么可以列出以下方程组：

\begin{cases} x+y=0 \\y+z=2 \\x+y+z=1 \end{cases}

但是不够严谨，因为我们没考虑“转过头”这种情况。即朝向为 $2$ 的方块旋转后会变为朝向 $0$ 。因此可以发现朝向存在模 $m$ 意义的同余关系。

上例方程组解得：

\begin{cases} x=-1\\y=1\\z=1 \end{cases}

出现了负数，怎么处理？

根据解的意义考虑，这相当于 $x$ 往回转一次，根据同余关系可以得到，往回转 $1$ 次就相当于向前转 $m-1$ 次。因此对于负数，采取 (x % m + m) % m 的方式即可转化为非负数。

于是题目就很明了了，让我们求出如下 $n$ 元一次同余方程组的解：

\begin{cases} x_1+x_2+x_3+\dots+x_n\equiv t_1-s_1\pmod m \\x_1+x_2+x_3+\dots+x_n\equiv t_2-s_2\pmod m \\\vdots \\x_1+x_2+x_3+\dots+x_n\equiv t_n-s_n\pmod m \end{cases}

因而可以用高斯消元求解。那么如何处理无数组解的情况呢？

高斯消元时我们会跳过一些零行。此时零行对应的变量就是一个自由元，可以任意赋值。

因此使用一个 ans 数组来存储答案，如果出现无数组解的情况，那么不管它，ans 数组也会自动赋值它为 $0$ 。

模意义下的除法显然需要用逆元解决，考虑到 $m$ 为质数，因此使用费马小定理计算。注意处处取模，答案不要忘了转化为 $[0,m)$ 内的数，还要开 long long。

1
#include <bits/stdc++.h>
2
#define N 110
3
#define SOLVE_OK 200
4
#define SOLVE_NO 404
5
#define LUXURIOUS_CHEST 0;
6
#define F return
7
using namespace std;
8

9
typedef long long ll;
10

11
int n, m;
12
ll matrix[N][N];
13
ll ans[N];
14

15
ll qpow(ll a, ll b, int p) {
16
    ll res = 1;
17
    while (b) {
18
        if (b & 1) res = res * a % p;
19
        a = a * a % p;
20
        b >>= 1;
21
    }
22
    return res % p;
23
}
24

25
ll inv(ll x, int p) {
26
    return qpow(x, p - 2, p);
27
}
28

29
int gauss() {
30
    // 1-index 高斯消元
31
    int rank = 0;
32
    for (int c = 1, r = 1; c <= n; c++) {
33
        int max_row = r;
34
        for (int i = r; i <= n; i++) {
35
            if (abs(matrix[i][c]) > abs(matrix[max_row][c])) {
36
                max_row = i;
37
            }
38
        }
39
        if (!matrix[max_row][c]) continue;
40
        if (max_row != r) swap(matrix[max_row], matrix[r]);
41
        for (int i = n + 1; i >= c; i--) {
42
            matrix[r][i] *= inv(matrix[r][c], m);
43
            matrix[r][i] = (matrix[r][i] % m + m) % m;
44
        }
45
        for (int i = r + 1; i <= n; i++) {
46
            if (abs(matrix[i][c])) {
47
                for (int j = n + 1; j >= c; j--) {
48
                    matrix[i][j] -= (matrix[r][j] * matrix[i][c]);
49
                    matrix[i][j] = (matrix[i][j] % m + m) % m;
50
                }
51
            }
52
        }
53
        r++;
54
        rank++;
55
    }
56
    if (rank < n) {
57
        // 无解判断
58
        for (int i = rank + 1; i <= n; i++) {
59
            for (int j = 1; j <= n + 1; j++) {
60
                if (abs(matrix[i][j])) return SOLVE_NO;
61
            }
62
        }
63
        // 无穷解处理，无穷解算作有解
64
        for (int i = 1; i <= n; i++) {
65
            for (int j = 1; j <= n; j++) {
66
                if (abs(matrix[i][j])) {
67
                    ans[j] = matrix[i][n + 1];
68
                    break;
69
                }
70
            }
71
        }
72
        return SOLVE_OK;
73
    }
74
    // 有唯一解，回代
75
    for (int i = n; i >= 1; i--) {
76
        for (int j = i + 1; j <= n; j++) {
77
            matrix[i][n + 1] -= (matrix[i][j] * matrix[j][n + 1]);
78
            matrix[i][n + 1] = (matrix[i][n + 1] % m + m) % m;
79
        }
80
    }
81
    for (int i = 1; i <= n; i++) ans[i] = matrix[i][n + 1];
82
    return SOLVE_OK;
83
}
84

85
int main() {
86
    ios::sync_with_stdio(false);
87
    cin.tie(nullptr);
88
    cout.tie(nullptr);
89

90
    cin >> n >> m;
91

92
    for (int i = 1; i <= n; i++) matrix[i][i] = 1; // 每个方块被击打后自己也会转一下，因此主对角线全为 1
93
    for (int i = 1; i <= n; i++) {
94
        int k;
95
        cin >> k;
96
        for (int j = 1; j <= k; j++) {
97
            int x;
98
            cin >> x;
99
            matrix[x][i] = 1;
100
        }
101
    }
102
    for (int i = 1; i <= n; i++) {
103
        ll s;
104
        cin >> s;
105
        matrix[i][n + 1] -= s;
106
    }
107
    for (int i = 1; i <= n; i++) {
108
        ll t;
109
        cin >> t;
110
        matrix[i][n + 1] += t;
111
    }
112
    int res = gauss();
113
    if (res == SOLVE_OK) {
114
        for (int i = 1; i <= n; i++) cout << (ans[i] % m + m) % m << ' ';
115
    } else cout << "niuza" << endl;
116

117
    F LUXURIOUS_CHEST
118
}

$\texttt{The End}$

音乐

JustPureH₂O

穷方圆平直之情，尽规矩准绳之用

音乐

P10315 [SHUPC 2024] - 原神，启动！题解

支持与分享

评论区

音乐

目录

音乐

JustPureH2O

穷方圆平直之情，尽规矩准绳之用

音乐

P10315 [SHUPC 2024] - 原神，启动！ 题解

支持与分享

评论区

音乐

目录

JustPureH₂O

P10315 [SHUPC 2024] - 原神，启动！题解