結果
問題 | No.2156 ぞい文字列 |
ユーザー |
|
提出日時 | 2023-03-18 16:13:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 1,467 bytes |
コンパイル時間 | 653 ms |
コンパイル使用メモリ | 87,228 KB |
最終ジャッジ日時 | 2025-02-11 15:11:53 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:58:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 58 | scanf("%lld", &n); | ~~~~~^~~~~~~~~~~~
ソースコード
#include<stdio.h> #include<string.h> #include<stdlib.h> #include <map> #include <vector> #include <queue> #include <deque> #include <set> #include <stack> #include <algorithm> #include <array> #include <unordered_set> #include <unordered_map> #include <string> using namespace std; bool rcmp(int a, int b) { return a>b; } typedef long long LL; class mypcmp { public: bool operator()(const int& a, const int& b) { return a<b; } }; #define MOD 998244353 int bb[2][2], mx[2][2], tmx[2][2]; int fib(LL n) { if (n<=1) return 1; int i, j, k; bb[0][0]=1; bb[0][1]=1; bb[1][0]=1; bb[1][1]=0; LL e=n-1; mx[0][0]=1; mx[0][1]=0; mx[1][0]=0; mx[1][1]=1; LL r, t, v; while(e) { if (e&1) { for (i=0; i<2; i++) for (j=0; j<2; j++) { v=0; for (k=0; k<2; k++) { t=mx[i][k]; t*=bb[k][j]; t%=MOD; v+=t; v%=MOD; } tmx[i][j]=v; } for (i=0; i<2; i++) for (j=0; j<2; j++) mx[i][j]=tmx[i][j]; } for (i=0; i<2; i++) for (j=0; j<2; j++) { v=0; for (k=0; k<2; k++) { t=bb[i][k]; t*=bb[k][j]; t%=MOD; v+=t; v%=MOD; } tmx[i][j]=v; } for (i=0; i<2; i++) for (j=0; j<2; j++) bb[i][j]=tmx[i][j]; e>>=1; } r=(mx[0][0]+mx[0][1])%MOD; return r; } int main() { int i; LL n; scanf("%lld", &n); // f[0]=1; f[1]=1; f[2]=2; ==> f[n]-1 printf("%d\n", (fib(n)-1+MOD)%MOD); return 0; }