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

提出ソース

結果

問題	No.840 ほむほむほむら
ユーザー	バイト
提出日時	2019-06-19 23:43:29
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	233 ms / 4,000 ms
コード長	12,226 bytes
コンパイル時間	1,532 ms
コンパイル使用メモリ	115,748 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-11-30 14:11:16
合計ジャッジ時間	3,198 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
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	23 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	9 ms 5,248 KB
testcase_08	AC	48 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	3 ms 5,248 KB
testcase_12	AC	16 ms 5,248 KB
testcase_13	AC	137 ms 5,248 KB
testcase_14	AC	21 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	4 ms 5,248 KB
testcase_17	AC	35 ms 5,248 KB
testcase_18	AC	182 ms 5,248 KB
testcase_19	AC	222 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	2 ms 5,248 KB
testcase_22	AC	4 ms 5,248 KB
testcase_23	AC	233 ms 5,248 KB
testcase_24	AC	5 ms 5,248 KB
testcase_25	AC	1 ms 5,248 KB
testcase_26	AC	5 ms 5,248 KB
testcase_27	AC	213 ms 5,248 KB

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

ソースコード

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 */
using vi = vector<int>;
//@formatter:off
template<typename T> T minv(T a, T m);
template<typename T> T minv(T a);

template<typename T>
class Modular {
public:
    using Type = typename decay<decltype(T::value)>::type;    constexpr Modular() : value() {}    template<typename U>    Modular(const U &x) {        value = normalize(x);    }    template<typename U>    static Type normalize(const U &x) {        Type v;        if (-mod() <= x && x < mod()) v = static_cast<Type>(x);        else v = static_cast<Type>(x % mod());        if (v < 0) v += mod();        return v;    }    const Type &operator()() const { return value; }    template<typename U>explicit operator U() const { return static_cast<U>(value); }    constexpr static Type mod() { return T::value; }    Modular &operator+=(const Modular &other) {        if ((value += other.value) >= mod()) value -= mod();        return *this;    }    Modular &operator-=(const Modular &other) {        if ((value -= other.value) < 0) value += mod();        return *this;    }    template<typename U> Modular &operator+=(const U &other) { return *this += Modular(other); }    template<typename U> Modular &operator-=(const U &other) { return *this -= Modular(other); }    Modular &operator++() { return *this += 1; }    Modular &operator--() { return *this -= 1; }    Modular operator++(signed) {        Modular result(*this);        *this += 1;        return result;    }    Modular operator--(signed) {        Modular result(*this);        *this -= 1;        return result;    }    Modular operator-() const { return Modular(-value); }
    template<typename U = T>typename enable_if<is_same<typename Modular<U>::Type, signed>::value, Modular>::type &operator*=(const Modular &rhs) {
#ifdef _WIN32
        uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;asm("divl %4; \n\t": "=a" (d), "=d" (m): "d" (xh), "a" (xl), "r" (mod()));value = m;
#else
        value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
        return *this;
    }
    template<typename U = T>    typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type &operator*=(const Modular &rhs) {        int64_t q = static_cast<int64_t>(static_cast<double>(value) * rhs.value / mod());        value = normalize(value * rhs.value - q * mod());        return *this;    }    template<typename U = T>    typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type &operator*=(const Modular &rhs) {        value = normalize(value * rhs.value);        return *this;    }    Modular &operator/=(const Modular &other) { return *this *= Modular(minv(other.value)); }    template<typename U> friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);    template<typename U> friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);    template<typename U> friend std::istream &operator>>(std::istream &stream, Modular<U> &number);    operator int() { return value; }private:    Type value;
};
template<typename T> bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value == rhs.value; }template<typename T, typename U> bool operator==(const Modular<T> &lhs, U rhs) { return lhs == Modular<T>(rhs); }template<typename T, typename U> bool operator==(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) == rhs; }template<typename T> bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) { return !(lhs == rhs); }template<typename T, typename U> bool operator!=(const Modular<T> &lhs, U rhs) { return !(lhs == rhs); }template<typename T, typename U> bool operator!=(U lhs, const Modular<T> &rhs) { return !(lhs == rhs); }template<typename T> bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value < rhs.value; }template<typename T> Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }template<typename T, typename U> Modular<T> operator+(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) += rhs; }template<typename T, typename U> Modular<T> operator+(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }template<typename T> Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }template<typename T, typename U> Modular<T> operator-(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) -= rhs; }template<typename T, typename U> Modular<T> operator-(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }template<typename T> Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }template<typename T, typename U> Modular<T> operator*(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) *= rhs; }template<typename T, typename U> Modular<T> operator*(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }template<typename T> Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }template<typename T, typename U> Modular<T> operator/(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) /= rhs; }template<typename T, typename U> Modular<T> operator/(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }

constexpr signed MOD =
        998244353;
//1e9 + 7;//MOD
using mint = Modular<std::integral_constant<decay<decltype(MOD)>::type, MOD>>;
constexpr int mint_len = 1400001;
vi fac, finv, inv;
vi p2;
mint com(int n, int r) {    if (r < 0 || r > n) return 0;    return mint(finv[r] * fac[n] % MOD * finv[n - r]);}
mint pom(int n, int r) {/*    if (!sz(fac)) com(0, -1);*/    if (r < 0 || r > n) return 0;    return mint(fac[n] * finv[n - 1]);}
mint npr(int n, int r) {/*    if (!sz(fac)) com(0, -1);*/    if (r < 0 || r > n) return 0;    return mint(fac[n] * finv[n - r]);}
int nprin(int n, int r) {/*    if (!sz(fac)) com(0, -1);*/    if (r < 0 || r > n) return 0;    return fac[n] * finv[n - r] % MOD;}
int icom(int n, int r) {    const int NUM_ = 1400001;    static ll fac[NUM_ + 1], finv[NUM_ + 1], inv[NUM_ + 1];    if (fac[0] == 0) {        inv[1] = fac[0] = finv[0] = 1;        for (int i = 2; i <= NUM_; ++i) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;        for (int i = 1; i <= NUM_; ++i) fac[i] = fac[i - 1] * i % MOD, finv[i] = finv[i - 1] * inv[i] % MOD;    }    if (r < 0 || r > n) return 0;    return ((finv[r] * fac[n] % MOD) * finv[n - r]) % MOD;}
#define ncr com
#define ncri icom
//n個の場所にr個の物を置く
mint nhr(int n, int r) { return com(n + r - 1, r); }
mint hom(int n, int r) { return com(n + r - 1, r); }
int nhri(int n, int r) { return icom(n + r - 1, r); }
template<typename T> T minv(T a, T m) {    T u = 0, v = 1;    while (a != 0) {        T t = m / a;        m -= t * a;        swap(a, m);        u -= t * v;        swap(u, v);    }    assert(m == 1);    return u;}
template<typename T> T minv(T a) {    if (a < mint_len)return inv[a];    T u = 0, v = 1;    T m = MOD;    while (a != 0) {        T t = m / a;        m -= t * a;        swap(a, m);        u -= t * v;        swap(u, v);    }    assert(m == 1);    return u;}
template<typename T, typename U> Modular<T> mpow(const Modular<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, typename U, typename V> mint mpow(const T a, const U b, const V m = MOD) {    assert(b >= 0);    int x = a, res = 1;    U p = b;    while (p > 0) {        if (p & 1) (res *= x) %= m;        (x *= x) %= m;        p >>= 1;    }    return res;}
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, typename U, typename V> int mpowi(const T &a, const U &b, const V &m = MOD) {    assert(b >= 0);    int x = a, res = 1;    U p = b;    while (p > 0) {        if (p & 1) (res *= x) %= m;        (x *= x) %= m;        p >>= 1;    }    return res;}
template<typename T> string to_string(const Modular<T> &number) {    return to_string(number());}
template<typename T> std::ostream &operator<<(std::ostream &stream, const Modular<T> &number) {    return stream << number();}
template<typename T> std::istream &operator>>(std::istream &stream, Modular<T> &number) {    typename common_type<typename Modular<T>::Type, int64_t>::type x;    stream >> x;    number.value = Modular<T>::normalize(x);    return stream;}



//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] * b[j];
    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;
}

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;
}

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

結果

テストケース

ソースコード