結果

問題 No.1516 simple 門松列 problem Re:MASTER
ユーザー MisterMister
提出日時 2021-05-21 22:39:06
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 631 ms / 6,000 ms
コード長 2,547 bytes
コンパイル時間 1,155 ms
コンパイル使用メモリ 91,044 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-18 16:08:39
合計ジャッジ時間 4,500 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 46 ms
5,376 KB
testcase_02 AC 275 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 12 ms
5,376 KB
testcase_07 AC 47 ms
5,376 KB
testcase_08 AC 66 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 14 ms
5,376 KB
testcase_11 AC 4 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 542 ms
5,376 KB
testcase_15 AC 253 ms
5,376 KB
testcase_16 AC 122 ms
5,376 KB
testcase_17 AC 42 ms
5,376 KB
testcase_18 AC 12 ms
5,376 KB
testcase_19 AC 6 ms
5,376 KB
testcase_20 AC 631 ms
5,376 KB
testcase_21 AC 618 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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, 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) + nn] = 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