結果
問題 | No.840 ほむほむほむら |
ユーザー |
|
提出日時 | 2019-06-14 22:27:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 161 ms / 4,000 ms |
コード長 | 1,568 bytes |
コンパイル時間 | 1,490 ms |
コンパイル使用メモリ | 169,412 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 06:47:32 |
合計ジャッジ時間 | 3,207 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include "bits/stdc++.h" using namespace std; typedef long long ll; const int INF = (1<<30); const ll INFLL = (1ll<<60); const ll MOD = (ll)(998244353ll); #define l_ength size void mul_mod(ll& a, ll b){ a *= b; a %= MOD; } void add_mod(ll& a, ll b){ a = (a<MOD)?a:(a-MOD); b = (b<MOD)?b:(b-MOD); a += b; a = (a<MOD)?a:(a-MOD); } int m; ll a[125][125],b[125][125],c[1][125]; void mulmat1(){ int i,j,k; for(i=0; i<m; ++i){ for(j=0; j<m; ++j){ b[i][j] = 0ll; } } for(i=0; i<m; ++i){ for(j=0; j<m; ++j){ for(k=0; k<m; ++k){ add_mod(b[i][j],(a[i][k]*a[k][j])%MOD); } } } for(i=0; i<m; ++i){ for(j=0; j<m; ++j){ a[i][j] = b[i][j]; } } } void mulmat0(){ int i,j,k; for(i=0; i<1; ++i){ for(j=0; j<m; ++j){ b[i][j] = 0ll; } } for(i=0; i<1; ++i){ for(j=0; j<m; ++j){ for(k=0; k<m; ++k){ add_mod(b[i][j],(c[i][k]*a[k][j])%MOD); } } } for(i=0; i<1; ++i){ for(j=0; j<m; ++j){ c[i][j] = b[i][j]; } } } int main(void){ int k,i,j,p,q,r; ll n,ans=0ll; cin >> n >> k; m = k*k*k; for(i=0; i<m; ++i){ p = i%k; q = (i/k)%k; r = (i/k)/k; ++p; p %= k; j = (r*k+q)*k+p; add_mod(a[i][j],1ll); p = i%k; q = (i/k)%k; r = (i/k)/k; q += p; q %= k; j = (r*k+q)*k+p; add_mod(a[i][j],1ll); p = i%k; q = (i/k)%k; r = (i/k)/k; r += q; r %= k; j = (r*k+q)*k+p; add_mod(a[i][j],1ll); } c[0][0] = 1ll; while(n){ if(n%2){ mulmat0(); } mulmat1(); n /= 2; } for(i=0; i<m; ++i){ p = i%k; q = (i/k)%k; r = (i/k)/k; if(!r){ add_mod(ans,c[0][i]); } } cout << ans << endl; return 0; }