题解：P10528 [XJTUPC2024] 崩坏：星穹铁道

· · 题解

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;
    }
}

完结撒花火~