結果
問題 | No.2156 ぞい文字列 |
ユーザー | kotatsugame |
提出日時 | 2022-12-09 21:27:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,024 bytes |
コンパイル時間 | 571 ms |
コンパイル使用メモリ | 68,692 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-14 20:03:35 |
合計ジャッジ時間 | 1,249 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#include<iostream> #include<atcoder/modint> using namespace std; #include<array> template<typename T,unsigned int N> struct Matrix{ array<array<T,N>,N>dat; array<T,N>&operator[](int i){return dat[i];} const array<T,N>&operator[](int i)const{return dat[i];} Matrix(){for(int i=0;i<N;i++)dat[i].fill(T(0));} static Matrix eye(){ Matrix res; for(int i=0;i<N;i++)res[i][i]=1; return res; } Matrix operator+(const Matrix&A)const{ Matrix res; for(int i=0;i<N;i++)for(int j=0;j<N;j++) res[i][j]=dat[i][j]+A[i][j]; return res; } Matrix operator*(const Matrix&A)const{ Matrix res; for(int i=0;i<N;i++)for(int k=0;k<N;k++)for(int j=0;j<N;j++) res[i][j]+=dat[i][k]*A[k][j]; return res; } Matrix pow(long long n)const{ Matrix a=*this,res=eye(); for(;n;a=a*a,n>>=1)if(n&1)res=res*a; return res; } }; using mint=atcoder::modint998244353; using mat=Matrix<mint,2>; int main() { long N;cin>>N; mat A; A[0][0]=A[1][0]=A[0][1]=1; A[1][1]=0; A=A.pow(N); cout<<(A[0][1]+A[1][1]-1).val()<<endl; }