結果
問題 | No.2156 ぞい文字列 |
ユーザー |
![]() |
提出日時 | 2022-11-13 17:07:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,288 bytes |
コンパイル時間 | 2,067 ms |
コンパイル使用メモリ | 193,752 KB |
最終ジャッジ日時 | 2025-02-08 19:57:01 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long longconst int mod = 998244353;void mul_matrix_2x2(int const (&m0)[4],int const (&m1)[4],int (&m_out)[4]){m_out[0] = (m0[0] * m1[0] + m0[1] * m1[2])%mod;m_out[1] = (m0[0] * m1[1] + m0[1] * m1[3])%mod;m_out[2] = (m0[2] * m1[0] + m0[3] * m1[2])%mod;m_out[3] = (m0[2] * m1[1] + m0[3] * m1[3])%mod;}void power_matrix_2x2(int const (&m0)[4],unsigned int const n,int (&m_out)[4]){if (n == 0) {m_out[0] = 1;m_out[1] = 0;m_out[2] = 0;m_out[3] = 1;} else if (n == 1) {m_out[0] = m0[0];m_out[1] = m0[1];m_out[2] = m0[2];m_out[3] = m0[3];} else if (n % 2 == 0) {int tmp_m[4];mul_matrix_2x2(m0, m0, tmp_m);power_matrix_2x2(tmp_m, n / 2, m_out);} else {int tmp_m_a[4];int tmp_m_b[4];mul_matrix_2x2(m0, m0, tmp_m_a);power_matrix_2x2(tmp_m_a, n / 2, tmp_m_b);mul_matrix_2x2(m0, tmp_m_b, m_out);}}int calculate_fibonacci(int n){int const matrix_2x2[4] = {1, 1, 1, 0};int result_matrix_2x2[4];power_matrix_2x2(matrix_2x2, n, result_matrix_2x2);return (result_matrix_2x2[2] + result_matrix_2x2[3])%mod;}signed main(){int N;cin>>N;cout<<(calculate_fibonacci(N)+mod-1)%mod<<endl;}