問題一覧 > 通常問題

No.2541 Divide 01 String

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 128
作問者 : ShirotsumeShirotsume / テスター : 👑 p-adicp-adic 👑 NachiaNachia
1 ProblemId : 9875 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-18 20:43:20

問題文

01 からなる長さ NN の文字列 SS が与えられます。

文字列 SS11 つ以上の空でない連続した文字列に分割する方法は全部で 2N12^{N-1} 通りありますが、そのうち、分割されてできる文字列すべてに 1 が少なくとも 11 つ含まれる方法はいくつありますか?

この答えを 998244353998244353 で割った余りを出力してください。

制約

  • 2N2×1052 \leq N \leq 2 \times 10^5
  • SS01 からなる長さ NN の文字列

入力

入力は標準入力から以下の形式で与えられる。

NN
SS

出力

答えを 998244353998244353 で割った余りを出力せよ。

サンプル

サンプル1
入力
3
101
出力
3

答えとなる分割の方法は、10, 1 と分ける方法と、1, 01 と分ける方法、101 と分ける方法の 33 つです。

サンプル2
入力
3
010
出力
1

答えとなる分割の方法は、010 と分ける方法の 11 つです。

サンプル3
入力
20
01001010101001010110
出力
7776

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