Problem:
 Score : 800 points    Problem Statement Given are integers N and X . For each integer k between 0 and X (inclusive), find the answer to the following question, then compute the sum of all those answers, modulo 998244353 .   Let us repeat the following operation on the integer k . Operation: if the integer is currently odd, subtract 1 from it and divide it by 2 ; otherwise, divide it by 2 and add 2^{N-1} to it. How many operations need to be performed until k returns to its original value? (The answer is considered to be 0 if k never returns to its original value.)       Constraints  1 \leq N \leq 2\times 10^5  0 \leq X < 2^N  X is given in binary and has exactly N digits. (In case X has less than N digits, it is given with leading zeroes.)  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  X       Output Print the sum of the answers to the questions for the integers between 0 and X (inclusive), modulo 998244353 .        Sample Input 1 3
111      Sample Output 1 40  For example, for k=3 , the operation changes k as follows: 1,0,4,6,7,3 . Therefore the answer for k=3 is 6 .       Sample Input 2 6
110101      Sample Output 2 616       Sample Input 3 30
001110011011011101010111011100      Sample Output 3 549320998

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
x = S()
rx=x.replace("1","2").replace("0","1").replace("2","0")
D = []
for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        if n // i % 2:
            D += [i]
        if i != n // i and i % 2:
            D += [n // i]

D.sort()
cnt = [0]*len(D)
ans=0
for k in range(len(D)):
    t=x[:D[k]]
    rt=rx[:D[k]]
    f=(t+rt)*(n//D[k]//2)+t
    cnt[k]=cnt[k]+int(f<=x)+int(t,2)
    cnt[k]%=mod
    ans += cnt[k]*D[k]*2
    ans%=mod
    for kk in range(k + 1, len(D)):
        if D[kk] % D[k] == 0:
            cnt[kk] -= cnt[k]
            cnt[kk]%=mod

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
x = S()
rx=x.replace("1","2").replace("0","1").replace("2","0")
D = []
for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        if n // i % 2:
            D += [i]
        if i != n // i and i % 2:
            D += [n // i]

D.sort()
cnt = [0]*len(D)
ans=0
for k in range(len(D)):
    t=x[:D[k]]
    rt=rx[:D[k]]
    f=(t+rt)*(n//D[k]//2)+t
    cnt[k]=cnt[k]+int(f<=x)+int(t,2)
    cnt[k]%=mod
    ans += cnt[k]*D[k]*2
    for kk in range(k + 1, len(D)):
        if D[kk] % D[k] == 0:
            cnt[kk] -= cnt[k]
            cnt[kk]%=mod

print(ans % mod)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
x = S()
rx=x.replace("1","2").replace("0","1").replace("2","0")
D = []
for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        if n // i % 2:
            D += [i]
        if i != n // i and i % 2:
            D += [n // i]

D.sort()
bx=int(x,2)
cnt = [0] * len(D)
ans = 0
for k in range(len(D)):
    t=x[:D[k]]
    rt=rx[:D[k]]
    f=(t+rt)*(n//D[k]//2)+t
    cnt[k]=cnt[k]+int(f<=x)+int(t,2)
    cnt[k]%=mod
    ans += cnt[k]*D[k]*2
    for kk in range(k + 1, len(D)):
        if D[kk] % D[k] == 0:
            cnt[kk] -= cnt[k]
            cnt[kk]%=mod
    ans %= mod

print(ans % mod)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
x = S()
rx=x.replace("1","2").replace("0","1").replace("2","0")
D = []
for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        if n // i % 2:
            D += [i]
        if i != n // i and i % 2:
            D += [n // i]

D.sort()
bx=int(x,2)
cnt = [0] * len(D)
ans = 0
for k in range(len(D)):
    t=x[:D[k]]
    rt=rx[:D[k]]
    f=(t+rt)*(n//D[k]//2)+t
    cnt[k]=cnt[k]+int(int(f,2)<=bx)+int(t,2)
    cnt[k]%=mod
    ans += cnt[k]*D[k]*2
    for kk in range(k + 1, len(D)):
        if D[kk] % D[k] == 0:
            cnt[kk] -= cnt[k]
            cnt[kk]%=mod
    ans %= mod

print(ans % mod)

Solution (Python):
def divisors(M):
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

def Ind(b,n):
    count=0
    while n%b==0:
        count+=1
        n//=b
    return count

N=int(input())
X=input()
x=0
for i in range(N):
    x=2*x+int(X[i])

a=Ind(2,N)
n=N//(2**a)
d=divisors(n)
data={i*2**(a+1):0 for i in d}
mod=998244353

for i in d:
    Q=((2**(i*2**a)+1)*(x+1))//(2**N+1)
    Q%=mod
    data[i*2**(a+1)]+=Q
    data[i*2**(a+1)]%=mod


for i in d:
    for j in d:
        if i>j and i%j==0:
            data[i*2**(a+1)]-=data[j*2**(a+1)]
            data[i*2**(a+1)]%=mod


ans=0
for i in data:
    ans+=data[i]*i
    ans%=mod
print(ans)

Solution (Python):
n = int(input())
s = input()
mod = 998244353
pr = []
for i in range(2,n+1):
  if n%i == 0:
    pr.append((i,n//i))
num = []
pr = pr[::-1]
for p,q in pr:
  if p%2 == 0:
    continue
  ntmp = 0
  x = s[:q]
  y = ""
  for i in x:
    if i == "0":
      y += "1"
    else:
      y += "0"
  for i in range(q):
    if x[i] == "1":
      ntmp = (ntmp+pow(2,q-1-i,mod))%mod
  k = (x+y)*((p-1)//2)+x
  if s >= k:
    ntmp += 1
  num.append((p,2*q,ntmp))
ans = 2*n
for i in range(n-1,-1,-1):
  if s[i] == "1":
    ans = (ans+pow(2,n-1-i,mod)*2*n)%mod
for i in range(len(num)):
  p1,x,number = num[i]
  for p2,y,number2 in num:
    if x == y:
      continue
    elif p2%p1 == 0 and (p2//p1)%2 == 1:
      number -= number2
  num[i] = p1,x,number
for p1,x,number in num:
  ans = (ans-(2*n-x)*number)%mod
print(ans)

Solution (Python):
MOD = 998244353
n = int(input())
x = input()

div = []
i = 1
while i*i <= n:
	if n%i == 0:
		if i%2 == 1:
			div.append(i)
		if i != n//i and (n//i) % 2 == 1:
			div.append(n//i)
	i += 1
div.sort(reverse=True)

ans = dict()

for d in div:
	l = n//d
	blocks = [int(x[i:i+l], 2) for i in range(0, n, l)]
	res = blocks[0]
	same = True
	tmp = blocks[0]
	for i, y in enumerate(blocks[1:]):
		tmp = ((1<<l)-1) ^ tmp
		if tmp < y:
			break
		elif tmp > y:
			same = False
			break
	ans[d] = (res + same) % MOD
	for dd in div:
		if dd == d:
			break
		elif dd % d == 0:
			ans[d] -= ans[dd]
			ans[d] %= MOD

print(sum([(2*n) // k * v for k, v in ans.items()]) % MOD)

Solution (Python):
import sys
from collections import Counter
readline = sys.stdin.readline

def divi(n):
    res = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n//i)
    return res

MOD = 998244353
N = int(readline())
X = list(map(int, readline().strip()))
D = divi(N)
C = Counter()
for d in D:
    if N//d % 2 == 0:
        continue
    res = 0
    for x in X[:d]:
        res = (2*res)%MOD
        res += x
    res += 1
    xx = X[:d] + [not x for x in X[:d]]
    for i in range(N):
        x1 = X[i]
        x2 = xx[i%(2*d)]
        if x1 == x2:
            continue
        if x1 < x2:
            res -= 1
            break
        break
    C[2*d] = res%MOD

CL = list(C.items())
CL.sort()
K = len(CL)
Kc, Vc = list(map(list, zip(*CL)))
for i in range(K):
    for j in range(i+1, K):
        if Kc[j] % Kc[i] == 0:
            Vc[j] = (Vc[j] - Vc[i])%MOD
ans = 0
for i in range(K):
    ans = (ans + Kc[i]*Vc[i])%MOD
print(ans)

Solution (Python):
"""n = 12
anoms = 0
for i in range(2**n):
    count = 0
    x=i
    while True:
        count += 1
        if x%2==1:
            x //= 2
        else:
            x //= 2
            x += 2**(n-1)
        if x == i:
            break
    if count != 2*n:
        t = bin(i)[2:]
        print("0"*(n-len(t))+t)
        anoms += 1


if x[0] == '0':
    k = 1
    while k<n and x[k] == '0':
        k += 1
    comp = "".join(str((i//k)%2) for i in range(n))
    if x < comp:
        k += 1
else:
    k = 1
    while k<n and x[k] == '1':
        k += 1
    comp = "".join(str((1+i//k)%2) for i in range(n))
    if x < comp:
        k -= 1"""


MOD = 998244353

n = int(input())
x = input()


def binToInt(x):
    result = 0
    t = 1
    i = 0
    while i < len(x):
        if x[~i] == '1':
            result += t
            result %= MOD
        i += 1
        t *= 2
        t %= MOD
    return result


def getCompStr(pref, copies):
    inv = "".join(str(1-int(c)) for c in pref)
    if copies%2 == 1:
        return (pref+inv)*(copies//2) + pref
    return (pref+inv)*(copies//2)


d = 1
factors = []
while d*d <= n:
    if n%d == 0:
        factors.append(d)
        if (d*d != n):
            factors.append(n//d)
    d += 1
factors.sort()

defects = 0
result = 0
computedDefects = {}
for size in factors:
    numComps = n//size
    if numComps%2==0 or numComps < 3:
        continue
    pref = x[:size]
    curDefects = binToInt(pref)
    for s in computedDefects:
        if size%s == 0 and (size//s)%2 == 1:
            curDefects -= computedDefects[s]
            curDefects %= MOD
    if getCompStr(pref, n//size) <= x:
        curDefects += 1
        curDefects %= MOD
    computedDefects[size] = curDefects
    defects += curDefects
    defects %= MOD
    result += curDefects*2*size
    result %= MOD


result += (binToInt(x)+1-defects)*2*n
result %= MOD
print(result)

Solution (Python):
MOD = 998244353

def getDivisors(x):
    anss = set()
    for d in range(1, int(x**0.5)+1):
        if x%d == 0:
            anss.add(d)
            anss.add(x//d)
    return sorted(anss)

N = int(input())
X = input()

divisors = getDivisors(2*N)

periods = [d for d in divisors if d%2 == 0 and (2*N//d)%2]
numP = len(periods)

anss = dict(zip(periods, [0]*numP))
for p in periods:
    lenPtn = p//2
    anss[p] += int(X[:lenPtn], 2) % MOD
    Ts = X[:lenPtn]
    notTs = ''.join(['1' if T == '0' else '0' for T in Ts])
    T2s = (Ts+notTs)*(N//p) + Ts
    if T2s <= X:
        anss[p] += 1
    anss[p] %= MOD
    for p2 in periods:
        if p == p2: continue
        if p2%p == 0:
            anss[p2] -= anss[p]

ans = sum([k*v for k, v in anss.items()])
print(ans % MOD)

Solution (Python):
n = int(input())
a = input()
inva = ''.join(map(lambda x: str(int(x) ^ 1), a))

mod = 998244353
ans = 0
p = 1
num = [0] * -~n
for i in range(n):
    if i:
        num[i] += (num[i - 1] * 2) % mod
    if a[i] == '1':
        num[i] += 1


def get_div(x):
    y = []
    for i in range(1, n):
        if x % i == 0 and (x // i) % 2:
            y.append(i)
    return y


div = get_div(n)
d = [0] * -~n
tot = 0
for i in div:
    now = n // i
    tt = num[i - 1]
    for j in get_div(i):
        tt -= d[j]
    k = (a[:i] + inva[:i]) * (n // (2 * i)) + a[:i]
    d[i] = tt + (a >= k)
    tot += d[i]
d[n] = int(a, 2) + 1 - tot

for i in range(n + 1):
    ans = (ans + d[i] * i * 2) % mod

print(ans % mod)

Solution (Python):
n=int(input())
X=input()
x=list(map(int,list(X)))
mod=998244353
pow_2=[0]*n
pow_2[n-1]=1
for i in range(1,n):
    pow_2[n-1-i]=(pow_2[n-i]*2)%mod
num=0
for i in range(n):
    if x[i]==1:
        num=(num+pow_2[i])%mod

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
li=make_divisors(n)
lst=[]
for i in li:
    if i%2==1 and i>2:
        lst.append(i)
lst.sort(reverse=True)
sum=0
count=0
s=[]
t=[]
for u in lst:
    U=u
    u=n//u
    cnt=0
    for i in range(1,u+1):
        if x[u-i]==1:
            cnt=(cnt+pow_2[-i])%mod
    y=list(X[:u])
    for i in range(u):
        if y[i]=="0":
            y.append("1")
        else:
            y.append("0")
    y="".join(y)
    y*=(U+1)//2
    y=y[:n]
    if y<=X:
        cnt+=1
    for i in range(len(s)):
        if u%s[i]==0:
            cnt-=t[i]
    sum=(sum+(2*cnt*u)%mod)%mod
    s.append(u)
    t.append(cnt)
    count=(count+cnt)%mod
print((((num+1-count)*2*n)%mod+sum)%mod)

Solution (Python):
import math
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353


N = int(sys.stdin.readline())
X = sys.stdin.readline().rstrip()
if len(X) != N:
    X = '0' * (N - len(X)) + X


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret



def test(N, X):
    def roll(k):
        if k & 1:
            k >>= 1
        else:
            k = (k >> 1) + 2 ** (N - 1)
        return k

    X = int(X, 2)
    ret = 0
    for K in range(X + 1):
        r = 1
        k = roll(K)
        while k != K:
            k = roll(k)
            r += 1
        ret += r
        if r != N * 2 or 1:
            import numpy as np
            print(np.binary_repr(k, N), r)
    return ret


def inv_s(x):
    """
    :param str x:
    """
    return ''.join(['0' if c == '1' else '1' for c in x])



def count(d):
    sz = N // d

    base = X[:sz] + inv_s(X[:sz])
    s = base * (N // sz)
    return int(X[:sz], 2) + (s <= X + inv_s(X))



counts = defaultdict(int)
counts[N * 2] = int(X, 2) + 1


ks = [N * 2 // d for d in get_divisors(N) if d % 2 and d != 1]
for k in ks:
    d = N * 2 // k
    counts[k] = count(d)



ans_counts = defaultdict(int)
for k in sorted(ks):
    ans_counts[k] = counts[k] - sum([ans_counts[d] for d in get_divisors(k)])
ans_counts[N * 2] = counts[N * 2] - sum([ans_counts[d] for d in get_divisors(N * 2)])

ans = 0
for k, cnt in ans_counts.items():
    ans += k * cnt
    ans %= MOD
print(ans)

Solution (Python):
import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter

import sys
def input():
	return sys.stdin.readline().strip()

N = int(input())
X = input()

def make_divisors(n):
	divisors = []
	for i in range(1, int(n**0.5)+1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n//i)
	return divisors

mod = 998244353
pow2 = [1]
for i in range(N):
	pow2.append((pow2[-1]*2) % mod)

yakusu_n = make_divisors(2*N)
yakusu_n.sort()



ans = 0
before = 0


num_dict = defaultdict(int)
for n in yakusu_n:
	if N % (2*n) != 0 and N % n == 0:
		num = 0
		for i in range(n):
			if X[i] == "1":
				num += pow2[n - 1 - i]
		Y = list(X[:n])
		for i in range(n):
			if Y[i] == "0":
				Y.append("1")
			else:
				Y.append("0")
		Y = "".join(Y)
		Y = Y*(N//n)
		Y = Y[0:N]
		if X >= Y:
			num += 1
		
		num_yakusu = make_divisors(n)
		for z in num_yakusu:
			num -= num_dict[z]
		num_dict[n] = num
		num *= 2*n
		num %= mod
		ans += num
		ans %= mod
		

print(ans)

Solution (Python):
def main():
    md = 998244353
    n = int(input())
    x = input()
    dd = []
    for d0 in range(1, n + 1):
        if n % d0 == 0:
            d1 = n // d0
            if d0 % 2: dd += [d0]
            if d1 % 2: dd += [d1]
        if d0 ** 2 >= n: break
    if len(dd) > 1 and dd[-1] == dd[-2]:
        del dd[-1]
    dd.sort(reverse=True)
    pp = []
    ori = int(x, 2)
    for i, d in enumerate(dd):
        k = n // d
        a = x[:k]
        pp += [int(a, 2)]
        na = "".join("0" if c == "1" else "1" for c in a)
        cor = int((a + na) * (d // 2) + a, 2)
        if cor <= ori: pp[-1] += 1
        for j in range(i):
            dj = dd[j]
            if dj % d == 0:
                pp[i] -= pp[j]
    
    
    ans = 0
    for d, p in zip(dd, pp):
        k = n // d
        ans = (ans + 2 * k * p) % md
    print(ans)

main()

Solution (Python):
mod = 998244353
N = int(input())
X = input()
X_ = []
for i in range(N):
    if X[i]=='0':
        X_.append('1')
    else:
        X_.append('0')
X_ = ''.join(X_)

d = []
for n in range(1,N+1):
    if N%n==0 and (N//n)%2==1:
        d.append(n)

p_d = {}

for n in d:
    p_d[n] = 0
    S = (X[:n]+X_[:n])*(N//n//2)+X[:n]
    p_d[n] += int(X[:n],2)%mod
    if S<=X:
        p_d[n] += 1

ans = 0
for i in range(len(d)):
    n = d[i]
    for j in range(i):
        m = d[j]
        if n%m==0:
            p_d[n] -= p_d[m]
    ans += p_d[n]*2*n
ans %= mod
print(ans)

Solution (Python):
mod = 998244353
N = int(input())
X = input()

d = []
for n in range(1,N+1):
    if N%n==0 and (N//n)%2==1:
        d.append(n)

p_d = {}

for n in d:
    p_d[n] = 0
    S = []
    for i in range(N):
        j = i//n
        if X[i%n]=='0':
            if j%2==0:
                S.append('0')
            else:
                S.append('1')
        else:
            if j%2==0:
                S.append('1')
            else:
                S.append('0')

    S = ''.join(S)
    s = X[:n][::-1]
    for i in range(n):
        if s[i]=='1':
            p_d[n] += pow(2,i,mod)
    if S<=X:
        p_d[n] += 1

ans = 0
for i in range(len(d)):
    n = d[i]
    for j in range(i):
        m = d[j]
        if n%m==0:
            p_d[n] -= p_d[m]
    ans += p_d[n]*2*n
ans %= mod
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline



class AtCoder:
    def main(self):
        N = int(input())
        X = input().rstrip()

        k_cycles = 0
        ans = 0
        L = []
        for k in self.make_divisors(N):
            if (N // k) % 2 != 0:
                first_k_bit = X[:k]
                first_k_bit_ = first_k_bit.replace("0", "2").replace("1", "0").replace("2", "1")
                check_target = first_k_bit + (first_k_bit_ + first_k_bit) * ((N // k - 1) // 2)
                k_cycle = int(first_k_bit, 2) + (int(check_target, 2) <= int(X, 2))

                for l, cnt in L:
                    if k % l == 0:
                        k_cycle -= cnt
                L.append((k, k_cycle))

                k_cycles += k_cycle
                ans += 2 * k * k_cycle

        ans += (int(X, 2) + 1 - k_cycles) * 2 * N

        print(ans % 998244353)

    def make_divisors(self, n: int):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)

        divisors.sort()
        return divisors



if __name__ == '__main__':
    AtCoder().main()

Solution (Python):
def change(s):
    ans = []
    for i in s:
        if i== "0":
            ans.append("1")
        else:
            ans.append("0")
    return "".join(ans)

n = int(input())
s = input()
MOD = 998244353


a = [0] * (n+1)
for i in range(1, n + 1):
    if n % i == 0:
        a[i] += int(s[0:i], 2)
        a[i] %= MOD
        si = int(s[0:i])
        change_si = int(change(s[0:i]))
        for j in range(n // i):
            if j % 2 == 0:
                if si < int(s[j*i:(j+1)*i]):
                    a[i] += 1
                    break
                if si > int(s[j*i:(j+1)*i]):
                    break
            else:
                if change_si < int(s[j*i:(j+1)*i]):
                    a[i] += 1
                    break      
                if change_si > int(s[j*i:(j+1)*i]):
                    break 
        else:
            a[i] += 1


for i in range(1, n + 1):
    for j in range(2*i, n + 1, i):
        if n % j == 0:
            a[j] -= a[i]


b = []
ans = 0
for i in range(1, n+1):
    if n % i == 0:
        if (n // i) % 2 == 1: 
                b.append(i)


for i in range(1, n+1):
    if n % i == 0:
        for tmp in b:
            if tmp % i == 0:
                ans += a[i] * 2*tmp
                ans %= MOD
                break
          
print(ans % MOD)

Solution (Python):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def nasu(x):
  t = make_divisors(x)
  c = 0
  for i in t:
    c += D[i]
  return c

def honya(x):
  y = 0
  k = 1
  for i in range(x - 1, -1, -1):
    if X[i]:
      y = (y + k) % MOD
    k = (k * 2) % MOD
  return y + honyaraka(x)

def honyaraka(x):
  cnt = 0
  for i in range(N // x):
    t = i % 2
    for j in range(x):
      if X[cnt] != (X[j] ^ t):
        if X[cnt] == 0:
          return 0
        else:
          return 1
      cnt += 1
  return 1


N = int(input())
X = list(map(int, input()))
MOD = 998244353

Y = 0
k = 1
for i in range(N - 1, -1, -1):
  if X[i]:
    Y = (Y + k) % MOD
  k = (k * 2) % MOD

D = [0] * (N + 1)
L = make_divisors(N)

cnt = 0
for i in L:
  if i != N and (N // i) % 2 == 1:
    D[i] = honya(i) - nasu(i)
    cnt += D[i]

D[N] = Y - cnt + 1

ans = 0
for i in L:
  ans = (ans + D[i] * i * 2) % MOD

print(ans)

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

mod=998244353

N=int(input())
X=input()

import math
xr=math.ceil(math.sqrt(N))

LIST=[]
for i in range(1,xr+1):
    if N%i==0:
        LIST.append(i)
        LIST.append(N//i)

REP=[l for l in set(LIST) if (N//l)%2==1 and l!=N]

REP.sort(reverse=True)


ANS=2*N*(int(X,2)+1)%mod

def invstr(X,r):
    return bin(int(X,2)^((1<<r)-1))[2:].zfill(r)

from collections import defaultdict
score=defaultdict(int)

for r in REP:
    score[r]+=2*r-2*N

    for j in REP:
        if r%j==0 and j<r:
            score[j]-=score[r]
  
for r in REP:
    sc=score[r]

    

    XSTR=X[:r]

    kosuu=int(XSTR,2)

    if (XSTR+invstr(XSTR,r))*(N//(r*2))+XSTR<=X:
        kosuu+=1

    ANS+=kosuu*sc

print(ANS%mod)

Solution (Python):
mod=998244353
import collections
n=int(input())
x=input()
ans=(2*n*(int(x,2)+1))%mod

def make_divisors(n):
  divisors=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      divisors.append(i)
      if i!=n//i:
        divisors.append(n//i)

  divisors.sort(reverse=True)
  return divisors
D=make_divisors(n)
CT=collections.defaultdict(int)
for d in D:
  if d%2==0 or d==1:
    continue
  else:
    k=n//d
    
    
    y=(2**n-2**k)//(2**k+1)

    
    
    ct=(int(x,2)-y)//(y+1)+1
    
    Dk=make_divisors(k)
    for dk in Dk:
      if dk<k:
        ct-=CT[dk]
    CT[k]=ct

    
    ans-=ct*2*(n-k)


print(ans%mod)

Solution (Python):
N = int(input())
X = input()
MOD = 998244353

ans = 0
memo = dict()











def get_oddivisor(n):
    '''nの約数のうち商が奇数のものを返す
    '''
    d = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i%2 == 1:
                d.add(n//i)
            if (n//i)%2 == 1:
                d.add(i)
    return d

D = list(get_oddivisor(N))
D.sort()

def alternate(x, n):
    '''x: 00101, y: 11010, z: (00101)(11010)... n times
    '''
    y = ('0'*len(x) + bin(int(x,2) ^ (2**len(x)-1))[2:])[-len(x):]
    z = (x + y) * (n//2)
    if n%2 == 1:
        z += x
    return z

for d in D:
    cnt = int(X[:d], 2)
    if int(X, 2) >= int(alternate(X[:d], N//d), 2):
        cnt += 1
    dd = list(get_oddivisor(d))
    for ddd in dd:
        if ddd != d:
            cnt -= memo[ddd]
    memo[d] = cnt
    ans += cnt * 2 * d
    ans %= 998244353

print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))





def use_divisors(n):
    l_divisors, r_divisors = [], []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if (n//i)%2:
                l_divisors.append(i)
            if i != n//i:
                if (n//(n//i))%2:
                    r_divisors.append(n//i)
    return l_divisors + r_divisors[::-1]
 
N = I()
X = str(input())
Xr = ''.join('1' if c=='0' else '0' for c in X)

divisors = use_divisors(2*N)
C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = Xr[:d//2]
    Tc = T+Tr
    count = int(T,2)
    if Tc*(N//d)+Tc[:N-d*(N//d)] <= X:
        count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

ans = 0
for d in divisors:
    ans += d*C[d]
    ans %= mod

print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



def use_divisors(n):
    l_divisors, r_divisors = [], []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if (n//i)%2:
                l_divisors.append(i)
            if i != n//i:
                if (n//(n//i))%2:
                    r_divisors.append(n//i)
    return l_divisors + r_divisors[::-1]
 
N = I()
X = str(input())
Xr = ''.join('1' if c=='0' else '0' for c in X)

divisors = use_divisors(2*N)
C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = Xr[:d//2]
    Tc = T+Tr
    count = int(T,2)
    if int(Tc*(N//d)+Tc[:N-d*(N//d)],2) <= int(X,2):
        count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

ans = 0
for d in divisors:
    ans += d*C[d]
    ans %= mod

print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



def use_divisors(n):
    l_divisors, r_divisors = [], []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if (n//i)%2:
                l_divisors.append(i)
            if i != n//i:
                if (n//(n//i))%2:
                    r_divisors.append(n//i)
    return l_divisors + r_divisors[::-1]
 
N = I()
X = str(input())
Xr = ''.join('1' if c=='0' else '0' for c in X)

ans = 0
divisors = use_divisors(2*N)
C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = Xr[:d//2]
    Tc = T+Tr
    count = int(T,2)
    if int(Tc*(N//d)+Tc[:N-d*(N//d)],2) <= int(X,2):
        count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

ans = 0
for d in divisors:
    ans += d*C[d]
    ans %= mod

print(ans)