[这是题目链接]: https://www.luogu.com.cn/problem/P10528

P10528 [XJTUPC 2024] 崩坏：星穹铁道

题目背景

Corycle 喜欢玩一个由米哈游自主研发的一款回合制战斗游戏———《崩坏：星穹铁道》。这片银河中有名为「星神」的存在，他们造就现实，抹消星辰，在无数「世界」中留下他们的痕迹。你将由此探索新的文明，结识新的伙伴，在无数光怪陆离的「世界」与「世界」之间展开新的冒险。所有你想知道的，都将在群星中找到答案。

题目描述

在游戏《崩坏：星穹铁道》中，你的队伍里会有四名角色轮流行动，所有角色共享用于施放战技的战技点。当战斗开始时，你会获得 $k$ 个战技点，且战技点的上限为 $5$ 个。每个角色行动时可选择进行普通攻击或者施放战技，进行普通攻击时会为全队增加一个战技点，当战技点达到上限时也可以进行普通攻击，但是此时不回复战技点。角色施放战技需要消耗一个战技点，当没有战技点时只能进行普通攻击而不可释放技能。

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

  1. 当角色行动时，只会进行普通攻击。

  2. 当角色行动时，若有战技点不少于 $1$ 则必定释放技能，否则进行普通攻击。

  3. 不对角色的行动进行限制。

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

输入格式

输入第一行有两个正整数 $n$ 和 $k$ ($1\le n\le 1\times 10^{18},0\le k\le 5$)，表示总行动次数与初始战技点数，用空格隔开。

第二行有四个用空格隔开的正整数 $a_1,a_2,a_3,a_4$ ($1 \le a_1,a_2,a_3,a_4 \le 3$)，表示四名角色的行动模式类型。

输出格式

输出仅一个整数，表示不同的行动方案数。

输入输出样例 #1

输入 #1

1
2
12 1
2 3 2 1

输出 #1

1
1

输入输出样例 #2

输入 #2

1
2
8 5
2 1 1 3

输出 #2

1
4

题意就是有4个角色，有4个行动模式，

  • 第一种只能普攻
  • 第二种在战技点不少于 $1$ 时则必定释放技能，否则进行普攻
  • 第三种是都可以

4名角色必须按顺序行动

输入格式

输入第一行有两个正整数 $n$ 和 $k$ ($1\le n\le 1\times 10^{18},0\le k\le 5$)，表示总行动次数与初始战技点数，用空格隔开。

第二行有四个用空格隔开的正整数 $a_1,a_2,a_3,a_4$ ($1 \le a_1,a_2,a_3,a_4 \le 3$)，表示四名角色的行动模式类型。

输出格式

输出仅一个整数，表示不同的行动方案数。(对 $998244353$ 取模)

思路

我们可以分别对这三种类型的角色分情况讨论
设$f[i][k]$表示第$i$个回合中还剩$k$个战技点数$(i>1)$

1. 第一种类型

  • $f[i][1]=f[i-1][0]$
  • $f[i][2]=f[i-1][1]$
  • $f[i][3]=f[i-1][2]$
  • $f[i][4]=f[i-1][3]$
  • $f[i][5]=f[i-1][4]+f[i-1][5]$

2. 第二种类型

  • $f[i][0]=f[i-1][1]$
  • $f[i][1]=f[i-1][2]+f[i-1][0]$
  • $f[i][2]=f[i-1][3]$
  • $f[i][3]=f[i-1][4]$
  • $f[i][4]=f[i-1][5]$

3. 第三种类型

  • $f[i][0]=f[i-1][1]$
  • $f[i][1]=f[i-1][0]+f[i-1][2]$
  • $f[i][2]=f[i-1][1]+f[i-1][3]$
  • $f[i][3]=f[i-1][2]+f[i-1][4]$
  • $f[i][4]=f[i-1][3]+f[i-1][5]$
  • $f[i][5]=f[i-1][4]+f[i-1][5]$

但是，我们再看题目数据范围，($1\le n\le 1\times 10^{18}$)
很显然我们用递推的方式肯定TLE
因此，我们就想到要用$O(logn)$复杂度的算法：矩阵快速幂！

我们可以把每种类型的矩阵构造出来，来进行状态的转移

1.第一种类型

2.第二种类型

3.第三种类型

由于$4$个角色按顺序行动，我们可以把$4$个分成一组，用一组的矩阵进行快速幂运算，也就是分成$n/4$组,至于剩下的$n$ mod $4$ 个剩余的最后单独乘即可，初始状态就是初始战技点那一项为$1$,其余全为$0$。
最后答案就是剩余战技点分别$0,1,2,3,4,5$的和（别忘记取模）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod =998244353;
int n,m;
int op[4];
int x[6][6];
int A[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
};
int B[6][6]=
{
    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
};
int C[6][6]=
{
    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 ans[6][6];
int st[1][6];
int res[1][6];
void mu(int a[][6],int b[][6])
{
    int t[6][6]={0};
    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]+a[i][k]*b[k][j])%mod;
            }
        }
    }
    for(int i=0;i<6;i++)
    {
        for(int j=0;j<6;j++)
        {
            a[i][j]=t[i][j];
        }
    }
}
void qpow(int n)
{
    while(n)
    {
        if(n&1)
        {
            mu(ans,x);
        }
        mu(x,x);
        n>>=1;
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>m;
    cin>>op[0]>>op[1]>>op[2]>>op[3];
    st[0][m]=1;
    for(int i=0;i<6;i++) ans[i][i]=x[i][i]=1;
    for(int i=0;i<4;i++)
    {
        if(op[i]==1) mu(x,A);
        else if(op[i]==2) mu(x,B);
        else mu(x,C);
    }
    qpow(n/4);
    int yu=n%4;
    for(int i=0;i<yu;i++)
    {
        if(op[i]==1) mu(ans,A);
        else if(op[i]==2) mu(ans,B);
        else mu(ans,C);
    }
    for(int i=0;i<1;i++)
    {
        for(int j=0;j<6;j++)
        {
            for(int k=0;k<6;k++)
            {
                res[i][j]=(res[i][j]+st[i][k]*ans[k][j])%mod;
            }
        }
    }
    int as=(res[0][0]+res[0][1]+res[0][2]+res[0][3]+res[0][4]+res[0][5])%mod;
    cout<<as;
    return 0;
}