問題一覧 > 通常問題

No.2279 OR Insertion

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 79
作問者 : magsta / テスター : miscalc
5 ProblemId : 9188 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-20 09:34:47

問題文

0 と 1 のみで作られた長さ NN の文字列 SS が与えられます。

SS を 11 個以上の文字列に分割することを考えます。 具体的には、SS の隣り合う文字の間は N−1N-1 個ありますが、これらの中から 00 個以上選び、選んだ全ての間で分割します。 分割の仕方は 2N−1\displaystyle 2^{N-1} 種類となります。それぞれの分割の仕方に対する以下の方法で算出される値の総和を 998244353998244353 で割った余りを求めてください。

  • 分割されたそれぞれの文字列を 22 進数整数とみなしたときの、それらの論理和 (OR)

入力

NN
SS

  • 1≤N≤40001 \leq N \leq 4000
  • SS は 0 と 1 からなる長さ NN の文字列である
  • NN は整数である

出力

求めた値を出力し、最後に改行せよ。

サンプル

サンプル1
入力
3
110
出力
13

{110},{1,10},{11,0},{1,1,0}\{110\}, \{1,10\}, \{11,0\}, \{1,1,0\} という 44 通りの分割の方法があります。それぞれの論理和 (OR) は以下のようになります。 (1010 進数で表現しています)

{110}→6,{1,10}→3,{11,0}→3,{1,1,0}→1\{110\}→6, \{1,10\}→3, \{11,0\}→3, \{1,1,0\}→1

よって、総和は 1313 となります。

サンプル2
入力
30
011100101010100001110100101010
出力
625160010

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