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

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

题目原型谜题解法浅究（的情况）

题目地址

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

基本思路是，让号方块分别击打次，使得最终每个方块都朝向位置。

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

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

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

上例方程组解得：

出现了负数，怎么处理？

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

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

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

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

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

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

#include <bits/stdc++.h>
#define N 110
#define SOLVE_OK 200
#define SOLVE_NO 404
#define LUXURIOUS_CHEST 0;
#define F return
using namespace std;

typedef long long ll;

int n, m;
ll matrix[N][N];
ll ans[N];

ll qpow(ll a, ll b, int p) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res % p;
}

ll inv(ll x, int p) {
    return qpow(x, p - 2, p);
}

int gauss() {
    // 1-index 高斯消元
    int rank = 0;
    for (int c = 1, r = 1; c <= n; c++) {
        int max_row = r;
        for (int i = r; i <= n; i++) {
            if (abs(matrix[i][c]) > abs(matrix[max_row][c])) {
                max_row = i;
            }
        }
        if (!matrix[max_row][c]) continue;
        if (max_row != r) swap(matrix[max_row], matrix[r]);
        for (int i = n + 1; i >= c; i--) {
            matrix[r][i] *= inv(matrix[r][c], m);
            matrix[r][i] = (matrix[r][i] % m + m) % m;
        }
        for (int i = r + 1; i <= n; i++) {
            if (abs(matrix[i][c])) {
                for (int j = n + 1; j >= c; j--) {
                    matrix[i][j] -= (matrix[r][j] * matrix[i][c]);
                    matrix[i][j] = (matrix[i][j] % m + m) % m;
                }
            }
        }
        r++;
        rank++;
    }
    if (rank < n) {
        // 无解判断
        for (int i = rank + 1; i <= n; i++) {
            for (int j = 1; j <= n + 1; j++) {
                if (abs(matrix[i][j])) return SOLVE_NO;
            }
        }
        // 无穷解处理，无穷解算作有解
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (abs(matrix[i][j])) {
                    ans[j] = matrix[i][n + 1];
                    break;
                }
            }
        }
        return SOLVE_OK;
    }
    // 有唯一解，回代
    for (int i = n; i >= 1; i--) {
        for (int j = i + 1; j <= n; j++) {
            matrix[i][n + 1] -= (matrix[i][j] * matrix[j][n + 1]);
            matrix[i][n + 1] = (matrix[i][n + 1] % m + m) % m;
        }
    }
    for (int i = 1; i <= n; i++) ans[i] = matrix[i][n + 1];
    return SOLVE_OK;
}

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++) matrix[i][i] = 1; // 每个方块被击打后自己也会转一下，因此主对角线全为 1
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++) {
            int x;
            cin >> x;
            matrix[x][i] = 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        ll s;
        cin >> s;
        matrix[i][n + 1] -= s;
    }
    for (int i = 1; i <= n; i++) {
        ll t;
        cin >> t;
        matrix[i][n + 1] += t;
    }
    int res = gauss();
    if (res == SOLVE_OK) {
        for (int i = 1; i <= n; i++) cout << (ans[i] % m + m) % m << ' ';
    } else cout << "niuza" << endl;

    F LUXURIOUS_CHEST
}

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

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