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



Sample input:
3
111


Sample output:
40

Submission status: Time Limit Exceeded

Solution code:
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)
        for j in range(n // i):
            if j % 2 == 0:
                if int(s[0:i]) < int(s[j*i:(j+1)*i]):
                    a[i] += 1
                    break
                if int(s[0:i]) > int(s[j*i:(j+1)*i]):
                    break
            else:
                if int(change(s[0:i])) < int(s[j*i:(j+1)*i]):
                    a[i] += 1
                    break      
                if int(change(s[0:i])) > 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: 有効周期
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)

Submission status: Time Limit Exceeded

Solution code:
import math
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):
  t = X[:x]
  y = int(t, 2)
  c = y
  k = y
  j = 0
  r = (1 << x) - 1
  for i in range(N // x):
    j = (j << x) + k
    k = k ^ r
  if Y >= j:
    c += 1
  return c

N = int(input())
X = input()
Y = int(X, 2)
MOD = 998244353

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)

Submission status: Time Limit Exceeded

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

ans = 0
memo = dict()

# def get_divisor(n):
#     '''nの約数を返す
#     '''
#     d = set()
#     for i in range(1, int(n**0.5)+1):
#         if n % i == 0:
#             d.add(i)
#             d.add(n//i)
#     return d

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)

Submission status: Time Limit Exceeded

Solution code:
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 odd_divisors(n):
    l_divisors, r_divisors = [], []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if i%2:
                l_divisors.append(i)
            if i != n//i:
                if (n//i)%2:
                    r_divisors.append(n//i)
    return r_divisors + l_divisors[::-1]

N = I()
X = str(input())

ans = 0
divisors = odd_divisors(N)
divisors = [2*N//x for x in divisors]
C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = ''.join('1' if c=='0' else '0' for c in T)
    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)

Submission status: Time Limit Exceeded

Solution code:
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())

ans = 0
divisors = use_divisors(2*N)

C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = ''.join('1' if c=='0' else '0' for c in T)
    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)

Submission status: Time Limit Exceeded

Solution code:
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):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if (n//i)%2:
                divisors.append(i)
            if i != n//i:
                if (n//(n//i))%2:
                    divisors.append(n//i)
    divisors.sort()
    return divisors

N = I()
X = str(input())

ans = 0
divisors = use_divisors(2*N)

C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = ''.join('1' if c=='0' else '0' for c in T)
    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)

Submission status: Time Limit Exceeded

Solution code:
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):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if (n//i)%2:
                divisors.append(i)
            if i != n//i:
                if (n//(n//i))%2:
                    divisors.append(n//i)
    divisors.sort()
    return divisors

N = I()
X = str(input())

ans = 0
divisors = use_divisors(2*N)

C = defaultdict(int)
for d in divisors:
    C[d] = 0

for d in divisors:
    T = X[:d//2]
    Tr = ''.join('1' if c=='0' else '0' for c in T)
    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)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline


    nn = int(input())
    x = input()

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

        divisors.sort(reverse = True)
        return divisors

    fact_n = make_divisors(nn)

    used = {}

    ans = 0

    for i in fact_n:
        num_len = int(nn/i)
        base = x[:num_len]
        can_divide = int(base, 2)+1
        for key, value in used.items():
            if num_len%key == 0:
                can_divide -= value
        if int(x) < int((base + format(2**num_len-1-int(base,2), 'b'))*int((i-1)/2)+base):
            can_divide -= 1
        used[num_len] = can_divide
        ans += can_divide*num_len*2
        ans = ans%998244353


    print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline


    nn = int(input())
    x = input()

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

        divisors.sort(reverse = True)
        return divisors

    fact_n = make_divisors(nn)

    used = {}

    ans = 0

    for i in fact_n:
        num_len = int(nn/i)
        can_divide = int(x[:num_len], 2)+1
        for key, value in used.items():
            if num_len%key == 0:
                can_divide -= value
        if int(x) < int((x[:num_len] + format(2**num_len-1-int(x[:num_len],2), 'b'))*int((i-1)/2)+x[:num_len]):
            can_divide -= 1
        used[num_len] = can_divide
        ans += can_divide*num_len*2


    print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(),2)
M = (1 << N) - 1
A = 0
for j in range(X+1):
  E = format(j,'b').zfill(N)
  C = format(M-j,'b').zfill(N)
  K = 0
  F = E + C + E
  s = False
  for i in range(1,N+1):
    if F[-(N+2*i):-(2*i)]==E:
      K = 2*i
      s = True
    if s:
      break
  A += K
print(A)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int("0b"+(input()),2)

def f(num):
    num0 = num
    a = []
    def checker(num2,b):
        if num2 in b:
            return False
        else:
            return True
    while checker(num,a):
        if num % 2 == 1:
            a.append(num)
            num = (num - 1)//2
        else:
            a.append(num)
            num = num//2 + 2**(n-1)
    if num0 in a:
        return a
    else:
        return []

c = [[[-1],0]]
for i in range (x+1):
    for j in range (len(c)):
        if i in c[j][0]:
            c[j][1] += 1
            break
        else:
            if j != len(c)-1:
                continue
            else:
                c.append([f(i),1])
                break

d = 0
for k in range(len(c)):
    d += (len(c[k][0])) * (c[k][1])

print(d%998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(),2)
M = 2**N-1
A = 0
for j in range(X+1):
  E = format(j,'b').zfill(N)
  C = format(M-j,'b').zfill(N)
  K = 0
  F = E + C + E
  s = False
  for i in range(1,N+1):
    if F[-(N+2*i):-(2*i)]==E:
      K = 2*i
      s = True
    if s:
      break
  A += K
print(A)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
X = input()
mod = 998244353


def calc_div_odd(N):
    div_odd = []
    for i in range(1, math.floor(N ** (1/2)) + 1):
        if N % i == 0:
            if i % 2 == 1:
                div_odd.append(i)
            if N // i != i:
                if (N // i) % 2 == 1:
                    div_odd.append(N//i)
    return div_odd


block_num_list = calc_div_odd(N)
block_num_list.sort()
ok_num = {x: 0 for x in block_num_list}
use_num = {x: 0 for x in block_num_list}
div_dict = {x: [] for x in block_num_list}
for block_num in block_num_list:
    block_len = N // block_num
    X_ref = X[:block_len]
    ok_num[block_num] += int(X_ref, 2) % mod
    X_ref_inv = ''
    for i in range(block_len):
        x = '0' if X_ref[i] == '1' else '1'
        X_ref_inv += x
    Y = (X_ref + X_ref_inv) * (block_num // 2) + X_ref
    flg = 1
    for x, y in zip(X, Y):
        if x == '1' and y == '0':
            break
        elif x == '0' and y == '1':
            flg = 0
            break
    if flg:
        ok_num[block_num] += 1

    # if int(X, 2) >= int((X_ref + X_ref_inv) * (block_num // 2) + X_ref, 2):
        # ok_num[block_num] += 1

    div_d_list = calc_div_odd(block_num)
    for div_d in div_d_list:
        if div_d != block_num:
            div_dict[block_num].append(div_d)

ans = 0
for block_num in reversed(block_num_list):
    block_len = N // block_num
    div_list = div_dict[block_num]
    use_num[block_num] = (use_num[block_num] + ok_num[block_num]) % mod
    for div in div_list:
        use_num[div] = (use_num[div] - use_num[block_num]) % mod
    ans = (ans + ((block_len * 2) * use_num[block_num])) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
X = input()
mod = 998244353


def calc_div_odd(N):
    div_odd = []
    for i in range(1, math.floor(N ** (1/2)) + 1):
        if N % i == 0:
            if i % 2 == 1:
                div_odd.append(i)
            if N // i != i:
                if (N // i) % 2 == 1:
                    div_odd.append(N//i)
    return div_odd


block_num_list = calc_div_odd(N)
block_num_list.sort()
ok_num = {x: 0 for x in block_num_list}
use_num = {x: 0 for x in block_num_list}
div_dict = {x: [] for x in block_num_list}
for block_num in block_num_list:
    block_len = N // block_num
    X_ref = X[:block_len]
    ok_num[block_num] += int(X_ref, 2) % mod
    X_ref_inv = ''
    for i in range(block_len):
        x = '0' if X_ref[i] == '1' else '1'
        X_ref_inv += x
    Y = (X_ref + X_ref_inv) * (block_num // 2) + X_ref
    flg = 1
    for x, y in zip(X, Y):
        if x == '1' and y == '0':
            break
        elif x == '0' and y == '1':
            flg = 0
            break
    if flg:
        ok_num[block_num] += 1

    # if int(X, 2) >= int((X_ref + X_ref_inv) * (block_num // 2) + X_ref, 2):
        # ok_num[block_num] += 1

    div_d_list = calc_div_odd(block_num)
    for div_d in div_d_list:
        if div_d != block_num:
            div_dict[block_num].append(div_d)

ans = 0
for block_num in reversed(block_num_list):
    block_len = N // block_num
    div_list = div_dict[block_num]
    use_num[block_num] += ok_num[block_num]
    for div in div_list:
        use_num[div] -= use_num[block_num]
    ans = (ans + ((block_len * 2) * use_num[block_num])) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
X = input()
mod = 998244353


def calc_div_odd(N):
    div_odd = []
    for i in range(1, math.floor(N ** (1/2)) + 1):
        if N % i == 0:
            if i % 2 == 1:
                div_odd.append(i)
            if N // i != i:
                if (N // i) % 2 == 1:
                    div_odd.append(N//i)
    return div_odd


block_num_list = calc_div_odd(N)
block_num_list.sort()
ok_num = {x: 0 for x in block_num_list}
use_num = {x: 0 for x in block_num_list}
div_dict = {x: [] for x in block_num_list}
for block_num in block_num_list:
    block_len = N // block_num
    X_ref = X[:block_len]
    ok_num[block_num] += int(X_ref, 2) % mod
    X_ref_inv = ''
    for i in range(block_len):
        x = '0' if X_ref[i] == '1' else '1'
        X_ref_inv += x
    if int(X, 2) >= int((X_ref + X_ref_inv) * (block_num // 2) + X_ref, 2):
        ok_num[block_num] += 1

    div_d_list = calc_div_odd(block_num)
    for div_d in div_d_list:
        if div_d != block_num:
            div_dict[block_num].append(div_d)

ans = 0
for block_num in reversed(block_num_list):
    block_len = N // block_num
    div_list = div_dict[block_num]
    use_num[block_num] += ok_num[block_num]
    for div in div_list:
        use_num[div] -= use_num[block_num]
    ans = (ans + ((block_len * 2) * use_num[block_num])) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

N = int(input())
X = int(input(), 2)


@lru_cache(maxsize=None)
def calc(k: int):
    if k % 2 == 0:
        k = (k // 2)
        k += pow(2, N - 1)
    else:
        k = (k - 1) // 2
    return k


total = 0
for x in range(X + 1):
    k = x
    org_k = x
    c = 0
    # print(x, c, bin(k))
    while True:
        k = calc(k)
        c += 1
        # print(c, bin(k))
        if k == org_k:
            break
    total += c
    # print()

print(total)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
"""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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)