2024年西安交通大学程序设计校赛

因为本人比较菜，所以只补赛时（校内训练赛）写了但没写出的题，完整题解可以参考洛谷的巨巨~：

https://www.luogu.com.cn/article/vzlnmec8

K.崩坏：星穹铁道

关键题面：Corycle 想成为星穹铁道高手，为此他需要对自己的配队了如指掌。由于角色有多种职业，同时为了方便 对角色类型进行定位，他把角色的行动模式分为了三种类型：

1. 当角色行动时，只会进行普通攻击。
2. 当角色行动时，若有战技点不少于 1 则必定释放技能，否则进行普通攻击。
3. 不对角色的行动进行限制。

现在 Corycle 开始了一场战斗，他想知道当队伍中的四名角色一共行动 n 次时，可能会有多少种不同的 行动方案。我们称两个行动方案不同，当且仅当存在至少一个回合中，两个方案里角色行为不同。这个 答案可能是一个很大的数，所以请将答案对 998244353 取模。

分析

由题目来看，这是一道状态机模型，可以考虑 dp，但是 dp 必然要枚举每一次行动和每个状态，复杂度为\(nk\)，显然无法过掉此题，此时我们又可以想到状态机的 一个常用优化法案：矩阵，因为矩阵可以代表某个状态满足固定条件乘矩阵转移到新状态。如图可以写出状态机模型和对应的矩阵方程（忽略我丑陋的字体）

而且每轮的行动方式和顺序固定，不妨以轮为单位进行矩阵相乘

还有就是我没学结构体深入的一些知识，所以先用的是函数加传参的方式解决，ac代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int mat[3][6][6]={
        {
        {0,1,0,0,0,0},
        {0,0,1,0,0,0},
        {0,0,0,1,0,0},
        {0,0,0,0,1,0},
        {0,0,0,0,0,1},
        {0,0,0,0,0,1}
        },
        {
        {0,1,0,0,0,0},
        {1,0,0,0,0,0},
        {0,1,0,0,0,0},
        {0,0,1,0,0,0},
        {0,0,0,1,0,0},
        {0,0,0,0,1,0}
        },
        {
        {0,1,0,0,0,0},
        {1,0,1,0,0,0},
        {0,1,0,1,0,0},
        {0,0,1,0,1,0},
        {0,0,0,1,0,1},
        {0,0,0,0,1,1}
        }
};
int a[6][6];
int w[4];
int n,kk;
void mul(int z[][6],int x[][6],int y[][6])
{
    static int t[6][6];
    memset(t,0,sizeof t);
    for(int i=0;i<6;++i)
        for(int j=0;j<6;++j)
            for(int k=0;k<6;++k)
                t[i][j]=(t[i][j]+x[i][k]*y[k][j])%mod;
    memcpy(z,t,sizeof t);
}
int qmi(int m[][6],int k)
{
    int f[6][6]={0};
    f[0][kk]=1;
    while(k)
    {
        if(k&1)mul(f,f,a);
        mul(a,a,a);
        k>>=1;
    }
    int c=n%4;
    for(int i=0;i<c;++i)
    {

        mul(f,f,mat[w[i]]);
    }
    int res=0;
    for(int i=0;i<6;++i)res=(res+f[0][i])%mod;
    return res;
}
signed main(){
    cin>>n>>kk;
    for(int i=0;i<6;++i)a[i][i]=1;
    for(int i=0;i<4;++i)
    {
        int x;cin>>x;
        x--;
        w[i]=x;
        mul(a,a,mat[x]);
    }
    cout<<qmi(a,n/4);

}

注意，此题 n 没有说整除 4，也就是还有剩余需要处理

O. 筛法

在算法竞赛的数论知识中，我们接触过埃拉托斯特尼筛法、线性筛法、莫比乌斯反演、杜教筛、Powerful Number 筛、Min_25 筛、洲阁筛等算法来帮助我们优化一些求和/连乘的复杂度，那么现在问题来了， 今天这道题将会使用到上述的哪个算法呢？ 现在给定正整数 n，需要你求

其中 [i ⊥ j] 表示 i, j 是否互素，即当 gcd(i, j) = 1 时，[i ⊥ j] 的值为 1，其余情况其值为 0。

分析

具体的分析和证明在洛谷大佬的题解中已有描述，我这里就在提一嘴赛时最容易但是很难想起的做法：打表。

因为此题的题面的迷惑性，让人觉得这题是有什么高深的算法从而忘记数论本身找规律的角度思考，只需要取一个小 n，很容易就发现规律\(n^2\)即为答案（隔壁队就是这样过的）