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

标签：matrix 星穹 题解 tr ret XJTUPC2024 mod dp size

求方案数，分多种情况，不难想到 DP。

设 \(dp_{i, j}\) 表示已经行动 \(i\) 次，剩余战技点个数为 \(j\) 的方案数，容易得到以下转移方程。

\(a_i = 1\) 时，有

\[dp_{i, j} = \begin{cases} 0, &j = 0, \\ dp_{i - 1, j - 1}, &1 \leqslant j \leqslant 4, \\ dp_{i - 1, j - 1} + dp_{i - 1, j}, &j = 5. \\ \end{cases} \]

\(a_i = 2\) 时，有

\[dp_{i, j} = \begin{cases} dp_{i - 1, j + 1}, &j = 0 \lor 2 \leqslant j \leqslant 4, \\ dp_{i - 1, j - 1} + dp_{i - 1, j + 1}, &j = 1, \\ 0, &j = 5. \\ \end{cases} \]

\(a_i = 3\) 时，有

\[dp_{i, j} = \begin{cases} dp_{i - 1, j + 1}, &j = 0, \\ dp_{i - 1, j - 1} + dp_{i - 1, j + 1}, &1 \leqslant j \leqslant 4, \\ dp_{i - 1, j - 1} + dp_{i - 1, j}, &j = 5. \\ \end{cases} \]

初始条件

\[dp_{0, k} = 1 \]

答案

\[\sum\limits_{i = 0}^5 dp_{n, i} \]

发现本题 \(n\) 可以达到 \(10^{18}\)，并且转移方程形式固定，显然要使用矩阵乘法优化转移，将上面的三个转移分别写成矩阵 \(T_1, T_2, T_3\)。将角色行动一个循环视为一个单元，一个单元内的转移 \(T\) 可以用 \(T_1, T_2, T_3\) 表示，矩阵乘法优化完整的单元之间的转移，最后将剩余的行动次数补足即可。即总体的转移形如

\[T^{\lfloor \frac n 4 \rfloor} \prod\limits_{i = 1}^{n \mod 4} T_{a_i} \]

时间复杂度 \(O(k \log n)\)，\(k\) 是矩阵乘法的常数。

#include <array>
#include <iostream>

typedef long long ll;

using namespace std;

const int mod = 998244353;

typedef array<ll, 6> vec;
typedef array<vec, 6> matrix;

inline ll operator*(const vec &v1, const vec &v2) {
    ll ret = 0;
    for (size_t i = 0; i < v1.size(); ++i)
        ret = (ret + v1[i] * v2[i] % mod) % mod;
    return ret;
}
inline vec operator*(const vec &v, const matrix &mat) {
    vec ret{};
    for (size_t i = 0; i < v.size(); ++i)
        for (size_t j = 0; j < mat.size(); ++j)
            ret[i] = (ret[i] + v[j] * mat[j][i] % mod) % mod;
    return ret;
}
inline matrix operator*(const matrix &m1, const matrix &m2) {
    matrix ret{};
    for (size_t i = 0; i < m1.size(); ++i)
        for (size_t j = 0; j < m2[0].size(); ++j)
            for (size_t k = 0; k < m2.size(); ++k)
                ret[i][j] = (ret[i][j] + m1[i][k] * m2[k][j] % mod) % mod;
    return ret;
}
inline matrix operator^(matrix mat, ll k) {
    matrix ret{};
    for (size_t i = 0; i < ret.size(); ++i)
        ret[i][i] = 1;
    while (k) {
        if (k & 1)
            ret = ret * mat;
        mat = mat * mat;
        k >>= 1;
    }
    return ret;
}

ll n, k;
int a[5];
matrix tr[4], trans;

static inline void solve() {
    tr[1][0][1] = tr[1][1][2] = tr[1][2][3] = tr[1][3][4] = tr[1][4][5] = tr[1][5][5] = 1;
    tr[2][5][4] = tr[2][4][3] = tr[2][3][2] = tr[2][2][1] = tr[2][1][0] = tr[2][0][1] = 1;
    tr[3][0][1] = tr[3][1][2] = tr[3][2][3] = tr[3][3][4] = tr[3][4][5] = tr[3][5][5] =
        tr[3][5][4] = tr[3][4][3] = tr[3][3][2] = tr[3][2][1] = tr[3][1][0] = 1;
    for (size_t i = 0; i < trans.size(); ++i)
        trans[i][i] = 1;
    cin >> n >> k;
    for (int i = 1; i <= 4; ++i) {
        cin >> a[i];
        trans = trans * tr[a[i]];
    }
    vec ans{};
    ans[k] = 1; // 初始化
    ans = ans * (trans ^ (n / 4)); // 整块的转移
    for (int i = 1; i <= n % 4; ++i) // 散块的转移
        ans = ans * tr[a[i]];
    int sum = 0;
    for (auto x : ans) // 统计答案
        sum = (sum + x) % mod;
    cout << sum << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

崩铁，启动！

标签：matrix,星穹,题解,tr,ret,XJTUPC2024,mod,dp,size
From： https://www.cnblogs.com/bluewindde/p/18375839