問題一覧 > 通常問題

No.2541 Divide 01 String

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

問題文

0 と 1 からなる長さ $N$ の文字列 $S$ が与えられます。

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

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

制約

  • $2 \leq N \leq 2 \times 10^5$
  • $S$ は 0 と 1 からなる長さ $N$ の文字列

入力

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

$N$
$S$

出力

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

サンプル

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

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

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

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

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

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