题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#pragma GCC optimize("2,3,Ofast,inline,unroll-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}
    
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

constexpr int P = 998244353;
using Z = MInt<P>;

const int N = 10 + 5, M = 170 + 5;

int T, m, K, S, id[N][N][N];
Z tmp[M], ans[M], Inv[N];

struct Matrix {
    Z a[M][M];
    Z* operator[](int x) {
        return a[x];
    }
} f[M];

Matrix operator*(Matrix x, Matrix y) {
    Matrix z;
    for (int i = 0; i <= S + 1; i++)
        for (int j = 0; j <= S + 1; j++) {
            z[i][j] = 0;
            for (int k = 0; k <= S + 1; k++)
                z[i][j] += x[i][k] * y[k][j];
        }
    return z;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> T >> m >> K;
    for (int i = 0; i <= K; i++)
        for (int j = 0; j <= (m > 1) * (K - i); j++)
            for (int k = 0; k <= (m > 2) * (K - i - j); k++)
                id[i][j][k] = ++S;
    for (int i = 0; i <= K; i++) {
        for (int j = 0; j <= (m > 1) * (K - i); j++) {
            for (int k = 0; k <= (m > 2) * (K - i - j); k++) {
                int D = (i + j + k < K);
                if (m == 1) {
                    if (i) f[0][id[i][j][k]][id[i - 1][j][k]] = (Z)i / (i + j + k + 1);
                } else if (m == 2) {
                    if (i) f[0][id[i][j][k]][id[i - 1][j][k]] = (Z)i / (i + j + k + 1);
                    if (j) f[0] [id[i][j][k]][id[i + 1][j - 1 + D][k]] = (Z)j / (i + j + k + 1);
                } else if (m == 3) {
                    if (i) f[0][id[i][j][k]][id[i - 1][j][k]] = (Z)i / (i + j + k + 1);
                    if (j) f[0][id[i][j][k]][id[i + 1][j - 1][k + D]] = (Z)j / (i + j + k + 1);
                    if (k) f[0][id[i][j][k]][id[i][j + 1][k - 1 + D]] = (Z)k / (i + j + k + 1);
                }
                f[0][id[i][j][k]][id[i][j][k]] = f[0][id[i][j][k]][S + 1] = (Z)1 / (i + j + k + 1);
            }
        }
    }
    f[0][S + 1][S + 1] = 1;
    for (int i = 1; i <= 60; i++)
        f[i] = f[i - 1] * f[i - 1];
    while (T--) {
        long long n;
        cin >> n;
        for (int i = 0; i <= S + 1; i++)
            ans[i] = 0;
        ans[id[m == 1][m == 2][m == 3]] = 1;
        for (int i = 0; i <= 60; i++) {
            if ((n >> i) & 1) {
                for (int j = 0; j <= S + 1; j++) {
                    tmp[j] = 0;
                    for (int k = 0; k <= S + 1; k++)
                        tmp[j] += ans[k] * f[i][k][j];
                }
                for (int j = 0; j <= S + 1; j++)
                    ans[j] = tmp[j];
            }
        }
        cout << ans[S + 1] << '\n';
    }
    return 0;
}