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

cao2333 · 2026-07-20 20:47:07 · 题解

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

同步发表于博客园(更好的阅读体验)。

前置知识：

1. 高斯消元（oi wiki）
2. 乘法逆元 (教练的blog)

前言

Update

2026.7.22 略加优化 （才发现写了题解没提交我还说怎么这么久都没过）

::::info[废话篇 ]

骗你的稻妻这个解谜我就没打过
话说让芽衣姐上岂不是更快，雷系一刀999诶
咳咳，停停停，我在说什么呢，这可是一篇正经题解啊awa
发现这个题还可以交题解，遂写此文咕咕咕
::::

题目背景

我看上面几个大佬大多数都是“显然”“容易得出”“可以想到”......
就，本蒟蒻还没搞清楚怎么想出来的，怎么就正解了？So，这篇文章主要写思路，废话较多，各位大佬和管理见谅~

题目传送门

现在有 n 个雷元素方碑，每个方碑都有 m 种不同状态(0,1, ···,m-1);

黄泉 可以选择任意一个方碑进行攻击，使单个方碑从 s 状态变成 s+1 状态 (特别的，若此时方碑为 m-1 状态，变为 0 状态);

同时，与它相连的 k_i 个方碑( a_1...a_{k_i})都会变成下一个状态（不会连锁），因为八雷飞渡是扩散技能，

现在，给定每个方碑的初始状态 s_i，当所有方碑全部达到指定状态 t_i 时视为解谜成功;

输入格式

\begin{matrix} &n &m\\ &k_1 &a_1 &a_2 &\dots &a_{k_1}\\ &k_2 &a_1 &a_2 &\dots &a_{k_2}\\ &\vdots &\vdots &&&\vdots\\ &k_n &a_1 &a_2 &\dots &a_{k_n}\\\\ &s_1 &s_2 &s_3 &\dots &s_n\\ &t_1 &t_2 &t_3 &\dots &t_n \end{matrix}

重要的数据范围

也就是说，他最后要求状态 t_i，就是 t_i=f_i+s_i\;\;(mod\;\;m).

那么有

把 s_i 挪到右边就变成典型的高斯消元啦 我一般喜欢打高斯-约旦消元2333

For不认得\sum的大佬：

也就是一楼大佬的式子喽 不知道你看着累不累反正我一行一行打是挺累的

正解

发现题目给的 n 很小，同时还有上面这坨系数方程组，每个节点都有一个操作次数 hit_i 作为 未知数(元)，我们就可以考虑 高斯消元 这个高级算法

由于\equiv两侧也是可以移项的，把 s_i 移到右边就可以啦，之后就是一个典型的高斯消元狸

矩阵长这样：

\begin{bmatrix} a_{1,1}&a_{2,1}&a_{3,1}&\dots&a_{n,1} &| &s_1-t_1\\ a_{1,2}&a_{2,2}&a_{3,2}&\dots&a_{n,2} &| &s_2-t_2\\ a_{1,3}&a_{2,3}&a_{3,3}&\dots&a_{n,3} &| &s_3-t_3\\ \vdots &\vdots&\vdots&\ddots &\vdots & &\vdots\\ a_{1,n}&a_{2,n}&a_{3,n}&\dots&a_{n,n} &| & s_n-t_n\\ \end{bmatrix}

不会打分割线有点丑大家凑合看吧QAQ

注意：

• 这个矩阵是在 mod\;m意义下的，在消元时一定要记得随时取模，除法不能直接模，记得写乘法逆元！
• 这里矩阵里的 a_{j,i} 刚刚好把行和列换过来了欧！！！在输入时一定要注意

然后就没啥了，就一个\mathcal{O(n^3)}的高斯消元或者高斯约旦消元+\mathcal{O(nlogm)}乘法逆元...

关于时间复杂度

是的楼上大佬 @sLMxf 时间复杂度算大了代码也错了多有冒犯还请见谅

不加标点的长难句+1

高斯消元没的说，就是：

• 遍历矩阵 i 行（方程）找主元
  • 遍历其他 j 行消元
    • 遍历j行的k列更新

明显是 \mathcal{O(n^3)}；

乘法逆元：

• 遍历每一行都会除以主元（系数化为一），一共n 个主元
  • 费马小定理快速幂O(logm)求逆元

明明就是 O(nlogm) 啊咕。

哪里来的n^2啊咕

关于无解

如果在处理过程中，发现某一行的元全部消掉但是等式右侧没有归为零的情况显然无解，需要 通知米哈游 输出 niuza(牛杂)

关于无穷多解

在处理过程中，若有一个元能被完全消去，即出现化简之后某一个 hit_i 系数为零的情况说明这个元能取任意值。但是这并不是无解。题目要求输出任意一组解，所以把这个值取为任意值即可 （要不让刻师傅歇一会设为0吧...）

提示tips

1. 切记: 十年OI一场空， __
2. 如果担心卡常可以试试快读。
3. 一定不要忘了消元常数项和最后输出处理.

::::success[ AC Code(注释版)]

//[email protected]
%:include<bits/stdc++.h>//这个能过欧~可以去搜一搜。
#define int long long//不开longlong见祖宗
using namespace std;
const int N=105;

int n,mod;//mod就是m
int K[N][N];//习惯用K表示系数矩阵，似乎不少人用a

void de(){//没用懒得删的debug调试咕
    cout<<"_______________\n";
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n+1; j++){
            cout<<K[i][j]<<" ";
        }
        cout<<endl;
    }
}

int ksm(int x, int k){//极简版子快速幂
    int ans=1;
    while(k){
        if(k&1) ans=ans*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return ans;
}

int inv(int x){//费马小定理求逆元
    return ksm(x,mod-2)%mod;//一定要模，逆元也可能炸
}
void gas_jod(){//高斯-约旦消元（气体约旦bush）

    for(int i=1; i<=n; i++){//循环遍历主元
        int t=i;            //记录用
        for(int j=i; j<=n; j++){//不可以往上找！上面的要留下来作答案
            if(abs(K[t][i])<abs(K[j][i])) t=j;//寻找一个绝对值最大的系数
        }
        if(t!=i) swap(K[t],K[i]);//直接换就行
        if(!K[i][i]) continue;   //若当前元为自由元，跳过即可，最后答案会消成0（没留为零就是无解）
        int div=inv(K[i][i]);    //计算乘法逆元
        for(int j=1; j<=n+1; j++){
            K[i][j]=(K[i][j]*div)%mod;
            //实际上是算K[i][j]/div%mod,即系数化为一
        }
        for(int j=1; j<=n; j++){ //循环每一个要消元的行，因为是高斯-约旦要遍历所有
            if(i==j)continue;
            int tmp=K[j][i];    //可以理解为消元的倍数
            for(int k=1; k<=n+1; k++){//循环 消元行的 所有系数
                K[j][k]=((K[j][k]-tmp*K[i][k]%mod)%mod +mod)%mod;
                //两式作差消去一元，一定要及时取模以及处理减法咕
            }
        }
    }
}
int t[N],s[N];//临时存一下，也用不着
signed main(){
    ios::sync_with_stdio(0);//关闭同步读入读出流
    cin.tie(0); cout.tie(0);//这东西肥肠好用！
    cin>>n>>mod;    //输入
    for(int i=1; i<=n; i++){
        int k;cin>>k;
        K[i][i]=1; //别忘了他自己是可以影响自己的
        for(int j=1; j<=k; j++){
            int num;cin>>num;
            K[num][i]=1;//记得要反着写，矩阵是歪的
        }
    }
    for(int i=1; i<=n; i++) cin>>s[i];
    for(int i=1; i<=n; i++){
        cin>>t[i];//读入
        K[i][n+1]=((t[i]-s[i])%mod+mod)%mod;//计算恒等式右边的结果
    }
    //gas_jod();//让我猜猜是谁写了函数没调用？
    //怎么是我啊QAQ
    for(int i=1; i<=n; i++){//检查是否无解
        if(!K[i][i]&&K[i][n+1]){
            cout<<"niuza\n";
            return 0;
        }
    }
  //因为之前可能跳过了某一个行，导致那一行的元没有消为零，所以要多除一次
    for(int i=1; i<=n; i++){
        cout<<K[i][n+1]/K[i][i]<<" ";
        //反正如果消得对也是除以1没什么影响嘛
    }
    return 0;
}

• 请注意部分防伪。
• Luogu数据太水了我一开始写错了输出没除以主元竟然还能过...

记录 ::::

题解就到这里，感 wo 谢 xiang 观 pian 看 zan，若有问题可以随时问咕

如果你还是 \color{red} W\!A 可以看看警示后人咕0w0