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

· · 题解

题目传送门

思路：

假设第 i 个方碑会被攻击 x_i 次，
且规定攻击第 i 个方碑后会带动第 j 个方碑一起进入下一个状态则 a_{i,j} 为 1，不会带动 a_{i,j} 为 0，
我们便可以列出以下方程组：

a_{1,1}x_1+a_{2,1}x_2+\cdots+a_{n,1}x_{n}+s_1\equiv t_1&(\operatorname{mod} m)\\ a_{1,2}x_1+a_{2,2}x_2+\cdots+a_{n,2}x_{n}+s_2\equiv t_2&(\operatorname{mod} m)\\ \cdots\\ a_{1,n}x_1+a_{2,n}x_2+\cdots+a_{n,n}x_{n}+s_n\equiv t_n&(\operatorname{mod} m) \end{cases}

把左边的 s_i 移项到右边：

a_{1,1}x_1+a_{2,1}x_2+\cdots+a_{n,1}x_{n}\equiv t_1-s_1&(\operatorname{mod} m)\\ a_{1,2}x_1+a_{2,2}x_2+\cdots+a_{n,2}x_{n}\equiv t_2-s_2&(\operatorname{mod} m)\\ \cdots\\ a_{1,n}x_1+a_{2,n}x_2+\cdots+a_{n,n}x_{n}\equiv t_n-s_n&(\operatorname{mod} m) \end{cases}

注意到 a_{i,j},s_{i},t_{i} 和 m 题目中已经给出，
于是就可以用高斯消元法解方程了。

注意在输出的时候要 \operatorname{mod} m。

Code:

#include <iostream>
#define int long long
using namespace std;
int n, m;
int a[105][105];
inline int upd(int x) {return (x % m + m) % m;}//处理负数
inline int inv(int x) {//保证m为素数，求费马小定理逆元
    int res(1), q(m - 2);
    while (q) {
        if (q & 1) res = res * x % m;
        x = x * x % m;
        q >>= 1;
    }
    return res;
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        a[i][i] = 1;//打自己的时候自己会进入下一个状态
        while (k--) {
            int x;
            cin >> x;
            a[x][i] = 1;
        }
    }
    for (int i = 1; i <= n; i++) cin >> a[i][n + 1];//a[i][n + 1]现在存的是s[i]
    for (int i = 1, x; i <= n; i++) cin >> x, a[i][n + 1] = upd(x - a[i][n + 1]);//a[i][n + 1]现在存的是t[i]-s[i]
    int r(1);
    for (int i = 1; i <= n; i++) {
        int pos(r);
        for (; pos <= n && !a[pos][i]; pos++);
        if (pos == n + 1) continue;//第i个未知数被消完 
        swap(a[r], a[pos]);
        int mul(inv(a[r][i]));
        for (int j = 1; j <= n; j++) {
            if (r != j && a[j][i]) {
                for (int k = n + 1; k >= i; k--) {
                    a[j][k] = upd(a[j][k] - a[r][k] * a[j][i] % m * mul % m);
                }
            }
        }
        r++;
    }
    if (r <= n) {
        for (int i = r; i <= n; i++) {//判断无解 
            bool f(0);
            for (int j = 1; j <= n; j++) f |= a[i][j];
            if (!f && a[i][n + 1]) cout << "niuza", exit(0);//0==a且a!=0的情况一定无解 
        }
    }
    r = 1;
    for (int i = 1; i <= n; i++) {
        cout << a[r][n + 1] * inv(a[r][i]) % m << ' ';
        a[r][n + 1] = 0;
        if (!a[r][i + 1]) r++;
    }
}

提交记录
点个赞再走罢

Update:

[2024/4/19] 修改 \LaTeX。
[2024/4/20] 题解被hack，修改了代码。