#352971 (C++14) No.840 ほむほむほむら

提出ソース

結果

問題	No.840 ほむほむほむら
ユーザー	バイト
提出日時	2019-06-19 23:47:08
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,358 bytes
コンパイル時間	1,480 ms
コンパイル使用メモリ	112,320 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-11-30 14:12:19
合計ジャッジ時間	3,315 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	5 ms 5,248 KB
testcase_03	AC	30 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	2 ms 5,248 KB
testcase_22	AC	5 ms 5,248 KB
testcase_23	WA	-
testcase_24	WA	-
testcase_25	AC	2 ms 5,248 KB
testcase_26	AC	6 ms 5,248 KB
testcase_27	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template<class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template<class T> struct _vec<T, 0> { using type = T; };
template<class T, size_t D> using vec = typename _vec<T, D>::type;
template<class T> vector<T> make_v(size_t size, const T &init) { return vector<T>(size, init); }
template<class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template<class T> inline void chmin(T &a, const T &b) { if (b < a) a = b; }
template<class T> inline void chmax(T &a, const T &b) { if (b > a) a = b; }
/* clang-format on */

//@formatter:off
constexpr
int MOD =  998244353;

struct mint {    int x;    mint() : x(0) {}    mint(int a) {        x = a % MOD;        if (x < 0) x += MOD;    }    mint &operator+=(mint that) {        x = (x + that.x) % MOD;        return *this;    }    mint &operator-=(mint that) {        x = (x + MOD - that.x) % MOD;        return *this;    }    mint &operator*=(mint that) {        x = (int) x * that.x % MOD;        return *this;    }    mint &operator/=(mint that) { return *this *= that.inverse(); }    mint operator-() { return mint(-this->x); }    friend ostream &operator<<(ostream &out, mint m) { return out << m.x; }    mint inverse() {        int a = x, b = MOD, u = 1, v = 0;        while (b) {            int t = a / b;            a -= t * b;            u -= t * v;            swap(a, b);            swap(u, v);        }        return mint(u);    }mint operator+(mint that) { return mint(*this) += that; }    mint operator-(mint that) { return mint(*this) -= that; }    mint operator*(mint that) { return mint(*this) *= that; }    mint operator/(mint that) { return mint(*this) /= that; }    bool operator ==(mint that) const { return x == that.x; }    bool operator !=(mint that) const { return x != that.x; }    bool operator <(mint that) const { return x < that.x; }    bool operator <=(mint that) const { return x <= that.x; }    bool operator >(mint that) const { return x > that.x; }    bool operator >=(mint that) const { return x >= that.x; }};
istream &operator>>(istream &i, mint &a) {    i >> a.x;    return i;}
typedef vector<mint> vm;
vector<mint> fac, finv;
int mint_len = 1400000;              //既に変更されていたら変えない
//void setmod(int mod = 1e9 + 7) {    if(MOD==1e9+7)MOD = mod;fac = vector<mint>(mint_len + 1);    finv = vector<mint>(mint_len + 1);    fac[0] = 1;    rep(i, 1, mint_len + 1) fac[i] = fac[i - 1] * i;    finv[mint_len] = (mint) 1 / fac[mint_len];    rer(i, mint_len, 1) finv[i - 1] = finv[i] * i;}
mint com(int a, int b) {    if (a < 0) return 0;    if (b < 0 || b > a) return 0;    return fac[a] * finv[a - b] * finv[b];}
mint hom(int a, int b) {    return com(a + b - 1, b);}
template<typename T, typename U>  mint mpow(const T a, const U b) {    assert(b >= 0);    int x = a, res = 1;    U p = b;    while (p > 0) {        if (p & 1) (res *= x) %= MOD;        (x *= x) %= MOD;        p >>= 1;    }    return res;}
template<typename T> inline mint mpow(const T a, const mint b) {    int x = a, res = 1;    int p = b.x;    while (p > 0) {        if (p & 1) (res *= x) %= MOD;        (x *= x) %= MOD;        p >>= 1;    }    return res;}
using PM = pair<mint, mint>;
using vm = vector<mint>;
#define vvm(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(mint,__VA_ARGS__)

#define smod setmod
//setmodを呼ぶ @formatter:on


//using mint = modint<998244353>;

typedef vector<mint> Vec;
typedef vector<Vec> Mat;

Mat eye(int n) {
    Mat I(n, Vec(n));
    for (int i = 0; i < n; ++i)
        I[i][i] = 1;
    return I;
}
Mat mul(Mat A, const Mat &B) {
    for (int i = 0; i < A.size(); ++i) {
        Vec x(A[0].size());
        for (int k = 0; k < B.size(); ++k)
            for (int j = 0; j < B[0].size(); ++j)
                x[j] += A[i][k] * B[k][j];
        A[i].swap(x);
    }
    return A;
}
Mat pow(Mat A, ll k) {
    Mat X = eye(A.size());
    for (; k > 0; k /= 2) {
        if (k & 1) X = mul(X, A);
        A = mul(A, A);
    }
    return X;
}
Vec mul(const Mat &A, const Vec &b) {
    Vec y(A.size());
    for (int i = 0; i < A.size(); ++i)
        for (int j = 0; j < A[0].size(); ++j)
            y[i] +=  A[i][j].x * b[j].x;
    return y;
}

ll solveNaive(int N, int K) {
    vec<mint, 3> dp = make_v(K, K, K, mint(0));
    dp[0][0][0] = 1;
    for (int t = 0; t < N; t++) {
        vec<mint, 3> ndp = make_v(K, K, K, mint(0));
        for (int a = 0; a < K; a++) {
            for (int b = 0; b < K; b++) {
                for (int c = 0; c < K; c++) {
                    mint cur = dp[a][b][c];
                    ndp[(a + 1) % K][b][c] += cur;
                    ndp[a][(a + b) % K][c] += cur;
                    ndp[a][b][(b + c) % K] += cur;
                }
            }
        }
        dp = ndp;
    }
    mint res = 0;
    for (int a = 0; a < K; a++) for (int b = 0; b < K; b++) res += dp[a][b][0];
    return res.x;
}

ll solve(int N, int K) {
    int dim = K * K * K;
    auto encode = [&](int a, int b, int c) {
        return a * K * K + b * K + c;
    };
    Mat A = make_v(dim, dim, mint(0));
    for (int a = 0; a < K; a++) {
        for (int b = 0; b < K; b++) {
            for (int c = 0; c < K; c++) {
                int cur = encode(a, b, c);
                A[encode((a + 1) % K, b, c)][cur] += 1;
                A[encode(a, (a + b) % K, c)][cur] += 1;
                A[encode(a, b, (b + c) % K)][cur] += 1;
            }
        }
    }
    A = pow(A, N);
    Vec init(dim);
    init[0] = 1;
    auto goal = mul(A, init);
    mint res = 0;
    for (int a = 0; a < K; a++) {
        for (int b = 0; b < K; b++) {
            res += goal[encode(a, b, 0)];
        }
    }
    return res.x;
}

int main() {
#ifdef DEBUG
    ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
    int N, K;
    while (cin >> N >> K) {
        cout << solve(N, K) << endl;
    }
    return 0;
}

yukicoder

結果

テストケース

ソースコード