結果

問題 No.840 ほむほむほむら
ユーザー mamekinmamekin
提出日時 2019-06-14 22:53:01
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 374 ms / 4,000 ms
コード長 4,462 bytes
コンパイル時間 1,185 ms
コンパイル使用メモリ 123,956 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-14 08:03:38
合計ジャッジ時間 4,020 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 9 ms
6,820 KB
testcase_03 AC 52 ms
6,816 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 3 ms
6,816 KB
testcase_07 AC 18 ms
6,816 KB
testcase_08 AC 93 ms
6,816 KB
testcase_09 AC 3 ms
6,816 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 4 ms
6,816 KB
testcase_12 AC 26 ms
6,816 KB
testcase_13 AC 243 ms
6,816 KB
testcase_14 AC 31 ms
6,820 KB
testcase_15 AC 2 ms
6,816 KB
testcase_16 AC 5 ms
6,820 KB
testcase_17 AC 56 ms
6,816 KB
testcase_18 AC 308 ms
6,820 KB
testcase_19 AC 374 ms
6,816 KB
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 2 ms
6,816 KB
testcase_22 AC 6 ms
6,820 KB
testcase_23 AC 359 ms
6,820 KB
testcase_24 AC 6 ms
6,820 KB
testcase_25 AC 2 ms
6,820 KB
testcase_26 AC 8 ms
6,816 KB
testcase_27 AC 358 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

template <class T1>
class Operators
{
public:
    template <class T2>
    const T1 operator+(const T2& right) const{
        T1 ans = static_cast<const T1&>( *this );
        return ans += right;
    }
    template <class T2>
    const T1 operator-(const T2& right) const{
        T1 ans = static_cast<const T1&>( *this );
        return ans -= right;
    }
    template <class T2>
    const T1 operator*(const T2& right) const{
        T1 ans = static_cast<const T1&>( *this );
        return ans *= right;
    }
    template <class T2>
    const T1 operator/(const T2& right) const{
        T1 ans = static_cast<const T1&>( *this );
        return ans /= right;
    }
    template <class T2>
    const T1 operator%(const T2& right) const{
        T1 ans = static_cast<const T1&>( *this );
        return ans %= right;
    }
    bool operator!=(const T1& right) const{
        const T1& left = static_cast<const T1&>( *this );
        return !(left == right);
    }
    bool operator>(const T1& right) const{
        const T1& left = static_cast<const T1&>( *this );
        return right < left;
    }
    bool operator<=(const T1& right) const{
        const T1& left = static_cast<const T1&>( *this );
        return !(right < left);
    }
    bool operator>=(const T1& right) const{
        const T1& left = static_cast<const T1&>( *this );
        return !(left < right);
    }
};

class Mod : public Operators<Mod>
{
private:
    static const int MOD = 998244353;
    long long a;
public:
    Mod(){
        a = 0;
    }
    Mod(long long x){
        a = (x % MOD + MOD) % MOD;
    }
    Mod& operator+=(const Mod& x){
        a = (a + x.a) % MOD;
        return *this;
    }
    Mod& operator-=(const Mod& x){
        a = (a - x.a + MOD) % MOD;
        return *this;
    }
    Mod& operator*=(const Mod& x){
        a = (a * x.a) % MOD;
        return *this;
    }
    Mod& operator/=(const Mod& x){ // フェルマーの小定理、MODが素数である場合のみ有効
        int b = MOD - 2;
        long long c = x.a;
        while(b > 0){
            if(b & 1){
                a *= c;
                a %= MOD;
            }
            c *= c;
            c %= MOD;
            b >>= 1;
        }
        return *this;
    }
    bool operator==(const Mod& x) const{
        return a == x.a;
    }
    long long getValue(){
        return a;
    }
};

// 行列の積
template <class T>
vector<vector<T> > matrixProduct(const vector<vector<T> >& x, const vector<vector<T> >& y)
{
    int a = x.size();
    int b = x[0].size();
    int c = y[0].size();
    vector<vector<T> > z(a, vector<T>(c, 0));
    for(int i=0; i<a; ++i){
        for(int j=0; j<c; ++j){
            for(int k=0; k<b; ++k){
                z[i][j] += x[i][k] * y[k][j];
            }
        }
    }
    return z;
}

// 行列の累乗
template <class T>
vector<vector<T> > matrixPower(const vector<vector<T> >& x, int k)
{
    int n = x.size();
    vector<vector<T> > y(n, vector<T>(n, 0));
    for(int i=0; i<n; ++i)
        y[i][i] = 1; // 積の単位元

    vector<vector<T> > z = x;
    while(k > 0){
        if(k & 1)
            y = matrixProduct(y, z);
        z = matrixProduct(z, z);
        k >>= 1;
    }
    return y;
}

int main()
{
    int n, k;
    cin >> n >> k;

    vector<vector<Mod> > mat(k*k*k, vector<Mod>(k*k*k, 0));
    for(int i=0; i<k*k*k; ++i){
        int a = i % k;
        int b = i / k % k;
        int c = i / k / k;

        for(int j=0; j<3; ++j){
            int a2 = a;
            int b2 = b;
            int c2 = c;
            if(j == 0)
                a2 = (a + 1) % k;
            else if(j == 1)
                b2 = (b + a) % k;
            else
                c2 = (c + b) % k;
            int i2 = (c2 * k + b2) * k + a2;
            mat[i2][i] += 1;
        }
    }
    mat = matrixPower(mat, n);

    Mod ans = 0;
    for(int i=0; i<k*k; ++i)
        ans += mat[i][0];
    cout << ans.getValue() << endl;

    return 0;
}
0