Submission #40872957

---

Source Code Expand

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)

const int N = 1e9, MOD = 998244353, INV6 = 166374059;

inline int mul(const int u, const int v) { return 1ll * u * v % MOD; }
inline void subeq(int& u, const int v) { (u -= v) < 0 && (u += MOD); }
inline int sub(int u, const int v) { return (u -= v) < 0 ? u + MOD : u; }
inline void addeq(int& u, const int v) { (u += v) >= MOD && (u -= MOD); }
inline int add(int u, const int v) { return (u += v) < MOD ? u : u - MOD; }
inline int mpow(int u, int v) {
    int ret = 1;
    for (; v; u = mul(u, u), v >>= 1) ret = mul(ret, v & 1 ? u : 1);
    return ret;
}

struct Matrix {
    static const int W = 6;
    int mat[W + 1][W + 1];

    inline int* operator [] (const int k) { return mat[k]; }

    inline Matrix operator * (const Matrix & u) const {
        Matrix ret{};
        rep (i, 0, W) rep (k, 0, W) rep (j, 0, W) {
            addeq(ret[i][j], mul(mat[i][k], u.mat[k][j]));
        }
        return ret;
    }
};

inline Matrix matpow(Matrix u, int v) {
    Matrix ret{};
    rep (i, 0, Matrix::W) ret[i][i] = 1;
    while (v) {
        if (v & 1) ret = ret * u;
        if (v >>= 1) u = u * u;
    }
    return ret;
}

const Matrix T = { {
    { 1 },
    { 0, 0, 1 },
    { 0, 0, 0, 1 },
    { 0, 0, 0, 0, 1 },
    { 0, 0, 0, 0, 0, 1 },
    { 0, 0, 0, 0, 0, 0, 1 },
    { 1, INV6, INV6, INV6, INV6, INV6, INV6 }
} };

inline Matrix init() {
    Matrix F[12] = {}; F[11] = matpow(T, N - 11);
    per (i, 10, 6) F[i] = F[i + 1] * T;
    per (i, 5, 0) F[i][6][6 - i] = 1;

    Matrix X{};
    X[0][0] = 1;
    rep (i, 1, 5) {
        X[i][i] = 6, X[i][6] = 6;
        rep (j, i + 1, i + 6) {
            addeq(X[i][6], F[j][6][0]);
            rep (k, 1, 6) subeq(X[i][6 - k], F[j][6][k]);
        }
    }

    rep (i, 0, 5) {
        int p = -1;
        rep (j, i, 5) if (X[j][i]) { p = j; break; }
        assert(~p);
        if (i != p) std::swap(X.mat[i], X.mat[p]);
        int inv = mpow(X[i][i], MOD - 2);
        rep (j, i + 1, 5) {
            int t = mul(inv, X[j][i]);
            rep (k, i, 6) subeq(X[j][k], mul(t, X[i][k]));
        }
    }
    per (i, 5, 0) {
        X[i][6] = mul(X[i][6], mpow(X[i][i], MOD - 2));
        rep (j, 0, i - 1) subeq(X[j][6], mul(X[j][i], X[i][6]));
    }

    Matrix F0 = { {
        { 1 },
        { X[5][6] }, { X[4][6] }, { X[3][6] },
        { X[2][6] }, { X[1][6] }, { X[0][6] }
    } };
    rep (i, 0, 5) fprintf(stderr, "%d%c", X[i][6], "\n "[i < 5]);
    return F0;
}

int main() {
    auto F0 = init();
    int m; scanf("%d", &m), m = N - m;
    if (m <= 5) printf("%d\n", F0[6 - m][0]);
    else printf("%d\n", (matpow(T, N - 1 - m + 1) * F0)[6][0]);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:98:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   98 |     int m; scanf("%d", &m), m = N - m;
      |            ~~~~~^~~~~~~~~~

Judge Result