B - Many 110 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

110 を 10^{10} 個連結した文字列を S とします（たとえば 110 を 3 個連結した文字列は 110110110 です）。

長さ N の文字列 T があります。

S に T が連続する部分文字列としていくつ含まれるかを求めてください。

制約

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

入力

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

N
T

出力

S に T が連続する部分文字列としていくつ含まれるかを出力せよ。

入力例 1

4
1011

出力例 1

9999999999

S は長いので、110 を 3 個連結した 110110110 に 1011 がいくつ含まれるかを考えます。 すると、

  • 1 1011 0110

  • 1101 1011 0

の 2 箇所に、1011 が連続する部分文字列として含まれています。

入力例 2

22
1011011011011011011011

出力例 2

9999999993

Score : 400 points

Problem Statement

Let S be the concatenation of 10^{10} copies of the string 110. (For reference, the concatenation of 3 copies of 110 is 110110110.)

We have a string T of length N.

Find the number of times T occurs in S as a contiguous substring.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • T is a string of length N consisting of 0 and 1.

Input

Input is given from Standard Input in the following format:

N
T

Output

Print the number of times T occurs in S as a contiguous substring.

Sample Input 1

4
1011

Sample Output 1

9999999999

S is so long, so let us instead count the number of times 1011 occurs in the concatenation of 3 copies of 110, that is, 110110110. We can see it occurs twice:

  • 1 1011 0110

  • 1101 1011 0

Sample Input 2

22
1011011011011011011011

Sample Output 2

9999999993