結果

問題 No.840 ほむほむほむら
ユーザー leaf_1415
提出日時 2019-06-14 22:56:35
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,040 ms / 4,000 ms
コード長 2,085 bytes
コンパイル時間 550 ms
コンパイル使用メモリ 66,316 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-14 12:41:44
合計ジャッジ時間 6,390 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <algorithm>
#include <vector>
#define llint long long
#define mod 998244353
using namespace std;
struct Matrix{
    int h, w;
    vector<llint> mat;
    Matrix(){
        h = w = 0;
    }
    Matrix(int h, int w){
        this->h = h, this->w = w;
        mat.resize(h*w);
    }
    llint& at(int i, int j){
        return mat[w*(i-1)+(j-1)];
    }
    static Matrix ident(int size){
        Matrix ret(size, size);
        for(int i = 1; i <= size; i++) ret.at(i, i) = 1;
        return ret;
    }
    Matrix operator*(Matrix& ope){
        Matrix ret(h, ope.w);
        for(int i = 1; i <= h; i++){
            for(int k = 1; k <= w; k++){
                if(at(i, k) == 0) continue;
                for(int j = 1; j <= ope.w; j++){
                    ret.at(i, j) += at(i, k) * ope.at(k, j) % mod;
                    ret.at(i, j) %= mod;
                }
            }
        }
        return ret;
    }
    Matrix pow(llint n){
        if(n == 0) return ident(h);
        if(n % 2){
            return pow(n-1) * (*this);
        }
        else{
            Matrix tmp = pow(n/2);
            return tmp * tmp;
        }
    }
    void print(){
        for(int i = 1; i <= h; i++){
            for(int j = 1; j <= w; j++){
                cout << at(i, j) << " ";
            }
            cout << endl;
        }
    }
};
llint n, x;
int main(void)
{
    cin >> n >> x;
    Matrix mat(x*x*x, x*x*x);
    
    llint ans = 0;
    for(int c = 0; c < x; c++){
        
        //cout << c << endl;
        
        for(int i = 1; i <= x*x*x; i++){
            for(int j = 1; j <= x*x*x; j++){
                mat.at(i, j) = 0;
            }
        }
        for(int i = 0; i < x; i++){
            for(int j = 0; j < x; j++){
                for(int k = 0; k < x; k++){
                    int s = i*x*x + j*x + k+1;
                    int ni = i, nj = j, nk = k, ns;
                    
                    ni = (i+1)%x, ns = ni*x*x + nj*x + nk + 1;
                    mat.at(ns, s) = 1;
                    ni = i;
                    
                    nj = (j+1)%x, ns = ni*x*x + nj*x + nk + 1;
                    mat.at(ns, s) = 1;
                    nj = j;
                    
                    int la = i, rc = (c-j+x)%x;
                    nk = k + la*rc%x, nk %= x;
                    ns = ni*x*x + nj*x + nk + 1;
                    mat.at(ns, s) = 1;
                }
            }
        }
        Matrix pmat = mat.pow(n);
        for(int i = 0; i < x; i++){
            for(int j = 0; j < x; j++){
                for(int k = 0; k < x; k++){
                    if(j != c || k != 0) continue;
                    int s = i*x*x + j*x + k + 1;
                    ans += pmat.at(1, s);
                    ans %= mod;
                }
            }
        }
    }
    cout << ans << endl;
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0