問題一覧 > 通常問題

No.2156 ぞい文字列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 135
作問者 : hibit_athibit_at / テスター : keisuke6keisuke6 MichirakaraMichirakara KowerKoint2010KowerKoint2010 kotamanegikotamanegi
5 ProblemId : 8813 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-06 09:20:36

問題文

Discord サーバー「あさかつ」では、コンテストの前に「ぞい」「ぞいぞい」「ぞぞい」等の発言をすることが常習化しています。

このような文字列は「ぞい文字列」と呼ばれます。

ぞい文字列を、以下の性質を満たす文字列として定義します。

  • 「ぞ」と「い」のみからなる文字列である。
  • 「ぞ」から始まる。
  • 「い」を少なくとも一文字含む。
  • 「い」が 2 つ連続してはならない。

正整数 $N$ が与えられるので、長さ $N$ のぞい文字列が何通りあるかを 998244353割ったあまりを答えてください。

入力

$N$

  • $N$ は整数
  • $2 \leq N \leq 10^{18}$

出力

整数 $1$ 行で出力してください。 最後に改行してください。

サンプル

サンプル1
入力
2
出力
1

ありえるぞい文字列は「ぞい」しかありません。

サンプル2
入力
4
出力
4

「ぞぞぞい」「ぞいぞい」「ぞぞいぞ」「ぞいぞぞ」の $4$ 通りが考えられます。

サンプル3
入力
100000
出力
56136313

ぞい文字列はそれなりに長いものである可能性があります。

998244353 で割ったあまりを出力してください。

サンプル4
入力
1000000000000000000
出力
332172356

ぞい文字列はとても長いものである可能性があります。

998244353 で割ったあまりを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。