Binary Strings are Fun (Codeforces 1762C)
Tags: Math, combinatorics

A binary string$$$^\dagger$$$ $$$b$$$ of odd length $$$m$$$ is good if $$$b_i$$$ is the median$$$^\ddagger$$$ of $$$b[1,i]^\S$$$ for all odd indices $$$i$$$ ($$$1 \leq i \leq m$$$).For a binary string $$$a$$$ of length $$$k$$$, a binary string $$$b$$$ of length $$$2k-1$$$ is an extension of $$$a$$$ if $$$b_{2i-1}=a_i$$$ for all $$$i$$$ such that $$$1 \leq i \leq k$$$. For example, 1001011 and 1101001 are extensions of the string 1001. String $$$x=$$$1011011 is not an extension of string $$$y=$$$1001 because $$$x_3 \neq y_2$$$. Note that there are $$$2^{k-1}$$$ different extensions of $$$a$$$.You are given a binary string $$$s$$$ of length $$$n$$$. Find the sum of the number of good extensions over all prefixes of $$$s$$$. In other words, find $$$\sum_{i=1}^{n} f(s[1,i])$$$, where $$$f(x)$$$ gives number of good extensions of string $$$x$$$. Since the answer can be quite large, you only need to find it modulo $$$998\,244\,353$$$.$$$^\dagger$$$ A binary string is a string whose elements are either $$$\mathtt{0}$$$ or $$$\mathtt{1}$$$.$$$^\ddagger$$$ For a binary string $$$a$$$ of length $$$2m-1$$$, the median of $$$a$$$ is the (unique) element that occurs at least $$$m$$$ times in $$$a$$$.$$$^\S$$$ $$$a[l,r]$$$ denotes the string of length $$$r-l+1$$$ which is formed by the concatenation of $$$a_l,a_{l+1},\ldots,a_r$$$ in that order.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), where $$$n$$$ is the length of the binary string $$$s$$$.The second line of each test case contains the binary string $$$s$$$ of length $$$n$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print the answer modulo $$$998\,244\,353$$$.

Note: In the first and second test cases, $$$f(s[1,1])=1$$$.In the third test case, the answer is $$$f(s[1,1])+f(s[1,2])=1+2=3$$$. In the fourth test case, the answer is $$$f(s[1,1])+f(s[1,2])+f(s[1,3])=1+1+1=3$$$.$$$f(\mathtt{11})=2$$$ because two good extensions are possible: 101 and 111.$$$f(\mathtt{01})=1$$$ because only one good extension is possible: 011.

Sample Inputs:
6
1
1
1
0
2
11
3
010
9
101101111
37
1011011111011010000011011111111011111

Sample Outputs:
1
1
3
3
21
365

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, s, m) = (readInt(), readStr(), 998244353)
    (ans, dp, cnt) = (1, 1, int(s[0]))
    for i in range(1, n):
        if s[i] == s[i - 1]:
            dp = 2 * dp % 998244353
        else:
            dp = 1
        ans += dp
    return ans % m
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys
import collections
import math
MOD = int(1000000000.0) + 7
MOD = 998244353
inf = 1e+20
input = sys.stdin.readline

def f():
    n = int(input())
    s = input()
    pre = 0
    c = 0
    res = 0
    for i in range(n):
        if pre != s[i]:
            c = 1
        else:
            c *= 2
        c %= MOD
        res += c
        pre = s[i]
    return res % MOD
for case in range(int(input())):
    print(f())

Solution (Python):
import bisect
import collections
import heapq
import io
import math
import os
import random
import sys
LO = 'abcdefghijklmnopqrstuvwxyz'
Mod = 998244353

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def euk(x, y):
    if y:
        (p, q, g) = euk(y, x % y)
        return (q, p - x // y * q, g)
    return (1, 0, x)
_input = lambda : sys.stdin.buffer.readline().strip().decode()
T = 1
T = int(_input())
for _ in range(T):
    n = int(_input())
    x = ''
    p = 1
    s = 0
    for y in _input():
        if x == y:
            p = p * 2 % Mod
        else:
            p = 1
            x = y
        s += p
    print(s % Mod)