結果
問題 |
No.3044 よくあるカエルさん
|
ユーザー |
|
提出日時 | 2025-02-28 22:40:14 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 86 ms / 2,000 ms |
コード長 | 880 bytes |
コンパイル時間 | 5,174 ms |
コンパイル使用メモリ | 332,392 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-28 22:40:23 |
合計ジャッジ時間 | 6,537 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=long long; using mint=modint998244353; int main() { int n,t; cin>>n>>t; int a,b; cin>>a>>b; mint p=a-1,q=b-a,r=7-b; p/=6;q/=6;r/=6; vector<vector<mint>> mt(t,vector<mint>(t)); mt[0][0]=p;mt[0][1]=q;mt[0][t-1]=r; for(int i=1;i<t;i++)mt[i][i-1]=1; n--; vector<vector<mint>> now(t,vector<mint>(t)); for(int i=0;i<t;i++)now[i][i]=1; auto prod=[t](auto x,auto y)->vector<vector<mint>>{ vector<vector<mint>> res(t,vector<mint>(t)); for(int i=0;i<t;i++)for(int j=0;j<t;j++)for(int k=0;k<t;k++)res[i][j]+=x[i][k]*y[k][j]; return res; }; while(n>0){ if(n&1){ now=prod(mt,now); } mt=prod(mt,mt); n>>=1; } cout<<now[0][0].val()<<endl; return 0; }