結果

問題 No.1112 冥界の音楽
コンテスト
ユーザー vjudge1
提出日時 2026-02-23 15:50:28
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,779 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,904 ms
コンパイル使用メモリ 192,700 KB
実行使用メモリ 1,484,360 KB
最終ジャッジ日時 2026-02-23 15:50:36
合計ジャッジ時間 8,732 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 3 MLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
const int mod=998244353;
const int INF=0x3f3f3f3f3f3f3f3f;
namespace Matrix{
	typedef vector<vector<int> > Mat;
	Mat init(int n,int c){return Mat(n,vector<int>(n,c));}
	void print(Mat a){
		cerr<<"---------------------------\n";
		for(auto x:a){
			for(auto y:x)cerr<<y<<" ";
			cerr<<"\n";
		}
		cerr<<"---------------------------\n";
		return;
	}
	Mat operator * (Mat a,Mat b){
		assert(a.size()==b.size());
		int n=a.size();
		Mat z=init(n,0);
		for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)z[i][j]=(z[i][j]+a[i][k]*b[k][j])%mod;
		return z;
	}
	Mat operator ^ (Mat a,int b){
		int n=a.size();
		Mat z=init(n,0);
		for(int i=0;i<n;i++)z[i][i]=1;
		while(b){
			if(b&1)z=z*a;
			a=a*a;
			b>>=1;
		}
		return z;
	}
}
using namespace Matrix;
int n,k;
int dot(int a,int b,int c){
    return a*k*k+b*k+c;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    // freopen("xyz.in","r",stdin);
    // freopen("xyz.out","w",stdout);
    cin>>n>>k;
    Mat a=init(k*k*k,0);
    Mat b=init(k*k*k,0);
    a[0][0]=1;
    for(int i=0;i<k;i++){
        for(int j=0;j<k;j++){
            for(int t=0;t<k;t++){
                b[dot((i+1)%k,j,t)][dot(i,j,t)]++;
                b[dot(i,(j+i)%k,t)][dot(i,j,t)]++;
                b[dot(i,j,(t+j)%k)][dot(i,j,t)]++;
            }
        }
    }
    // print(b);
    a=(b^n)*a;
    // print(a);
    int ans=0;
    for(int i=0;i<k;i++){
        for(int j=0;j<k;j++){
            ans=(ans+a[dot(i,j,0)][0])%mod;
        }
    }
    cout<<ans<<"\n";
    return 0;
}
/*
dp[i][j][t] 'X'=i (mod k),'XY'=j (mod k),'XYZ'=t (mod k)
dp[i+1][j][t] <- dp[i][j][t]
dp[i][(j+i)%k][t] <- dp[i][j][t]
dp[i][j][(t+j)%k] <- dp[i][j][t]

*/
0