自动搬运

查看原文

来自洛谷，原作者为

	Ratio_Y 善于隐藏自己的精明，才称得上是最大的精明。——拉罗什福科《道德箴言录》||主页跳转https://www.luogu.com.cn/paste/gaajjpsj

搬运于2025-08-24 22:58:53，当前版本为作者最后更新于2024-05-29 11:43:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upd on 6.5 更改了递推式错误以及部分格式错误。

---

崩坏：星穹铁道

题链 这么简单做不对不许玩崩铁！

题目大意

给你行动的总次数 $n$ 和初始战技点数量 $k$，以及编队里四名角色的行动类型，求不同行动方式的方案数。

类型见题面。

思路

先考虑 dp，分角色类型讨论。

设 $f_{i,k}$ 表示第 $i$ 动，剩 $j$ 个点。

当 $a=1$ 时，由于角色只能打点，点数上限为 $5$，所以得到：

$$f_{i,k}= \begin{cases} f_{i-1,k-1} (k\neq0) \\ f_{i-1,5} (k=5) \end{cases} $$

当 $a=2$ 时，角色有点耗点，没点打点，能得到：

$$f_{i,k}= \begin{cases} f_{i-1,k+1} (k\neq5) \\ f_{i-1,k-1} (k=1) \end{cases} $$

当 $a=3$ 时，角色既能打点，也能耗点，且满足战技点的范围，得到：

$$f_{i,k}= \begin{cases} f_{i-1,k+1} (k\neq 5) \\ f_{i-1,k-1} (k\neq0) \\f_{i-1,k} (k=5) \end{cases} $$

结合三者，即可得到状态转移方程。

那么复杂度为 $O(n)$，题目中 $n\le10^{18}$，男蚌。

怎么加速？矩阵快速幂！

矩阵怎么找？简单。把不同情况的转移结果按表格列出来，发现：标 $1$ 的是转移结果，也就是动后的点数。

结果如下：

$$T_1=\left[ \begin{matrix} 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 \\ \end{matrix} \right] $$$$T_2=\left[ \begin{matrix} 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 \\ \end{matrix} \right] $$$$T_3=\left[ \begin{matrix} 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 \\ \end{matrix} \right] $$

其中 $T_i$ 表示 $i$ 类型的角色。

再根据 dp，定义 $C_i=C_{i-1}\times T_{a_i}$。

这样快速幂结果为 $ans=C_4^{\lfloor {\frac{n}{4}} \rfloor}\times C_{n \,mod \,4}$。

答案为 $\sum_{i=0}^5 ans_{0,i}$。

注意

开 long long 啊！

code：

const int mod=998244353;
ll n,k,hksr;
ll a[5];
struct rmm
{
    ll a[6][6];
    rmm(){memset(a,0,sizeof a);}
}T[4],unit,B;
rmm operator*(const rmm &a,const rmm &b)
{//重载矩阵乘
    rmm ans;
    fo(i,0,5)
        fo(j,0,5)
            fo(k,0,5)
                ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
    return ans;
}
namespace Wisadel
{
    rmm Wqp(rmm a,ll b)
    {//矩阵快速幂
        rmm ans;
        ans=unit;
        while(b)
        {
            if(b&1ll)
                ans=ans*a;
            a=a*a;
            b>>=1ll;
        }
        return ans;
    }
    short main()
	{
        n=qr,k=qr;
        T[1].a[0][1]=T[1].a[1][2]=T[1].a[2][3]=T[1].a[3][4]=T[1].a[4][5]=T[1].a[5][5]=1;
        T[2].a[1][0]=T[2].a[0][1]=T[2].a[2][1]=T[2].a[3][2]=T[2].a[4][3]=T[2].a[5][4]=1;
        T[3].a[0][1]=T[3].a[1][2]=T[3].a[2][3]=T[3].a[3][4]=T[3].a[4][5]=T[3].a[5][5]=1,
        T[3].a[1][0]=T[3].a[0][1]=T[3].a[2][1]=T[3].a[3][2]=T[3].a[4][3]=T[3].a[5][4]=1;
        unit.a[0][0]=unit.a[1][1]=unit.a[2][2]=
        unit.a[3][3]=unit.a[4][4]=unit.a[5][5]=1;
        B=unit;
        //unit 是1矩阵（初始矩阵） 乘任何矩阵等于它本身
        fo(i,1,4)
            a[i]=qr,B=B*T[a[i]];
        rmm R,ans;
        R.a[0][k]=1;
        ans=R*Wqp(B,n/4);
        for(int i=0;i<n%4;i++)
            ans=ans*T[a[i%4+1]];
        //这是少算的那部分
        fo(i,0,5)
            hksr=(hksr+ans.a[0][i])%mod;
        printf("%lld\n",hksr);
        //Honkai: Star Rail！
        return Ratio;
	}
}

完结撒花火~