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

· · 题解

简述题面

给定 n 个 m 种状态的方碑（状态种类为 0\sim m-1），编号为 1\sim n。

第 i 个方碑的初始状态为 s_i，目标状态为 t_i。

每次操作可以选一个方碑，使它切换到下一种状态。但方碑有时会相互影响，当某一方碑被操作时，能被它影响的方碑也会切换到下一种状态（m−1 的下一个状态是 0）。

思路

很典的高斯消元题目，我们设第 i 个方碑被操作次数为 x_i，则有：

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

其中的 a_{i,j} 表示 j 号方碑是否会影响到 i 号方碑。

将各式的 s_i 移项可得：

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

于是我们便可以用高斯消元直接求解。

代码实现

因为我们平时所做的高斯消元一般是浮点型计算，而本题需要取模，所以可能会有一些实现细节的不同。

我们发现我们在消元期间做除法的目的就是让某一行的某个参 a_{i,j} 消为 0，于是我们可以将两式通分，即使两式的第 j 项均成为它们的最小公倍数，后统一做减法，即可绕开除法直接消元。

但最后也有绕不开的除法（在高斯消元逐步递推 x_i 时），我们不得不求解逆元。

:::success[AC Code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline long long power(long long a,long long b,long long m){
    long long res=1;
    for (;b;b>>=1,a=(a*a)%m)
        if (b&1) res=(res*a)%m;
    return res;
}
const int N=105;
int n,m;
int a[N][N];
int s[N],t[N];
inline int Gauss(int (*a)[N],int n){
    int rk=1;
    for (int j=1;j<=n;j++){
        int h=rk;
        for (int i=rk+1;i<=n;i++)
            if (abs(a[i][j])>abs(a[h][j])) h=i;
        if (a[h][j]==0) continue;
        for (int l=j;l<=n+1;l++)
            swap(a[j][l],a[h][l]);
        for (int i=rk+1;i<=n;i++){
            if (a[i][j]==0) continue;
            int g=__gcd(a[i][j],a[rk][j]);
            int tmp1=a[rk][j]/g;
            int tmp2=a[i][j]/g;
            for (int l=j;l<=n+1;l++)
                a[i][l]=((a[i][l]*tmp1-a[rk][l]*tmp2)%m+m)%m;//通分后消元
        }
        ++rk;
    }
    for (int i=rk;i<=n;i++)
        if (a[i][n+1]) return -1;
    for (int i=n;i>=1;i--){
        for (int j=i+1;j<=n;j++)
            a[i][n+1]=((a[i][n+1]-a[i][j]*a[j][n+1])%m+m)%m;
        a[i][n+1]=(a[i][n+1]*power(a[i][i],m-2,m))%m;//用逆元做模数除法
    }
    return 1;
}
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
inline void solve(){
    memset(a,0,sizeof(a));
    cin>>n>>m;
    for (int i=1,k;i<=n;i++){
        cin>>k;
        a[i][i]=1;
        for (int j=1,x;j<=k;j++){
            cin>>x;
            a[x][i]=1;//第 i 号石碑可以影响第 x 号石碑
        }
    }
    for (int i=1;i<=n;i++) cin>>s[i],a[i][n+1]=-s[i];
    for (int i=1;i<=n;i++) cin>>t[i],a[i][n+1]=((a[i][n+1]+t[i])%m+m)%m;//注意模数减法的实现
    int res=Gauss(a,n);
    if (res==-1) cout<<"niuza",exit(0);//无解情况
    for (int i=1;i<=n;i++)
        cout<<a[i][n+1]<<' ';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T=1;
    while (T--) solve(); 
    return 0;
}

:::