結果

問題 No.1516 simple 門松列 problem Re:MASTER
コンテスト
ユーザー Mister
提出日時 2021-05-21 22:35:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,521 bytes
コンパイル時間 1,193 ms
コンパイル使用メモリ 85,992 KB
最終ジャッジ日時 2025-01-21 15:43:12
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/modint>
#include <iostream>
#include <vector>

template <class T>
struct Matrix : public std::vector<std::vector<T>> {
    // constructor
    using std::vector<std::vector<T>>::vector;

    Matrix(int h, int w, T val = 0) {
        this->resize(h);
        for (auto& v : *this) v.resize(w, val);
    }

    static Matrix id(int n) {
        Matrix m(n, n);
        for (int i = 0; i < n; ++i) m[i][i] = 1;
        return m;
    }

    // arithmetic
    Matrix operator*(const Matrix& m) const { return Matrix(*this) *= m; }
    Matrix& operator*=(const Matrix& m) {
        int h1 = this->size(),
            h2 = m.size(),
            w2 = m.front().size();

        Matrix nmat(h1, w2);
        for (int i = 0; i < h1; ++i) {
            for (int j = 0; j < w2; ++j) {
                for (int k = 0; k < h2; ++k) {
                    nmat[i][j] += (*this)[i][k] * m[k][j];
                }
            }
        }
        return *this = nmat;
    }

    template <class U>
    Matrix pow(U k) {
        Matrix ret = id(this->size());
        Matrix a = *this;

        while (k > 0) {
            if (k & 1) ret *= a;
            a *= a;
            k >>= 1;
        }
        return ret;
    }
};

using namespace std;
using mint = atcoder::modint998244353;

bool judge(int i, int j, int k) {
    return ((i > j && j < k) || (i < j && j > k)) && i != k;
}

void solve() {
    int n, m;
    cin >> n >> m;

    auto enc = [&](int i, int j) { return i * m + j; };
    int nn = m * m;

    Matrix<mint> mat(nn * 2);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k < m; ++k) {
                if (!judge(i, j, k)) continue;

                int s = enc(i, j), t = enc(j, k);
                mat[t][s] = 1;
                mat[t + nn][s + nn] = 1;
                mat[t + nn][s] = k;
            }
        }
    }

    mat = mat.pow(n - 2);

    vector<mint> vec(nn * 2, 0);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i == j) continue;
            vec[enc(i, j)] = 1;
            vec[enc(i, j) + n] = i + j;
        }
    }

    mint cans = 0, sans = 0;
    for (int i = 0; i < nn * 2; ++i) {
        mint s = 0;
        for (int j = 0; j < nn * 2; ++j) {
            s += mat[i][j] * vec[j];
        }
        (i < nn ? cans : sans) += s;
    }

    cout << cans.val() << " " << sans.val() << "\n";
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    solve();

    return 0;
}
0