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: Wrong Answer

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 = int(S(), 2)
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)):
    bit = x >> (n - D[k])
    r_bit=(1<<D[k])-1^bit
    cnt[k] = (cnt[k] + bit) % mod
    m = 0
    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: Wrong Answer

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 = int(S(), 2)
D = []
for i in range(1, n + 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)):
    bit = x >> (n - D[k])
    cnt[k] = (cnt[k] + bit) % mod
    m = 0
    for i in range(n // D[k]):
        m <<= D[k]
        if i % 2:
            m |= ~bit
        else:
            m |= bit
    if m <= x:
        cnt[k] += 1
    ans += cnt[k] * D[k] * 2
    for kk in range(k + 1, len(D)):
        if D[kk] % D[k] == 0:
            cnt[kk] -= cnt[k]
    ans %= mod

print(ans % mod)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

mod = 998244353
n = int(input())
k = int(input())

ans = 0
cnt = pow(2, n, mod)

for i in range(1,n):
  if (i//gcd(i,(n-i)%i)) %2 == 0:
    ans += i*pow(2, gcd(i,(n-i)%i), mod)
    ans %= mod
    cnt -= pow(2, gcd(i,(n-i)%i), mod)
    cnt %= mod

ans += 2*n*cnt
ans %= mod

print(ans)

Submission status: Wrong Answer

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 p1,x,number in num:
  for p2,y,number2 in num:
    if x == y:
      continue
    elif p2%p1 == 0 and (p2//p1)%2 == 1:
      number -= number2
  ans = (ans-(2*n-x)*number)%mod
print(ans)

Submission status: Wrong Answer

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 p1,x,number in num:
  for p2,y,number2 in num:
    if x == y:
      continue
    elif p2%p1 == 0 and (p2//p1)%2 == 1:
      number -= number2
  ans -= (2*n-x)*number
print(ans%mod)

Submission status: Wrong Answer

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((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 x,number in num:
  for y,number2 in num:
    if x == y:
      continue
    elif x%y == 0 and (x//y)%2 == 1:
      number -= number2
  ans -= (2*n-x)*number
print(ans%mod)

Submission status: Wrong Answer

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((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 x,number in num:
  for y,number2 in num:
    if x == y:
      continue
    elif x%y == 0 and (x//y)%2 == 1:
      number -= number2
  ans -= (2*n-x)*number
print(ans)

Submission status: Wrong Answer

Solution code:
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
    sum=(sum+(2*cnt*u)%mod)%mod
    count=(count+cnt)%mod
print((((num+1-count)*2*n)%mod+sum)%mod)

Submission status: Wrong Answer

Solution code:
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]
    print(S)
    print(X)
    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)

Submission status: Wrong Answer

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

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

p_d = {}

for n in d:
    p_d[n] = 0
    l = N//n
    s = X[:l]
    s_ = ''
    for i in range(l):
        if s[i]=='0':
            s_ = s_+'1'
        else:
            s_ = s_+'0'
    S = []
    for i in range(n):
        if i%2==0:
            S.append(s)
        else:
            S.append(s_)
    S = ''.join(S)
    s = s[::-1]
    for i in range(l):
        if s[i]=='1':
            p_d[n] += pow(2,i,mod)
    if S<=X:
        p_d[n] += 1

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

Submission status: Wrong Answer

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

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

p_d = {}

for n in d:
    p_d[n] = 0
    l = N//n
    s = X[:l]
    s_ = ''
    for i in range(l):
        if s[i]=='0':
            s_ = s_+'1'
        else:
            s_ = s_+'0'
    S = []
    for i in range(n):
        if i%2==0:
            S.append(s)
        else:
            S.append(s_)
    S = ''.join(S)
    s = s[::-1]
    for i in range(l):
        if s[i]=='1':
            p_d[n] += pow(2,i,mod)
    if S<=X:
        p_d[n] += 1

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

Submission status: Wrong Answer

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

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

p_d = {}

for n in d:
    p_d[n] = 0
    l = N//n
    s = X[:l]
    s_ = ''
    for i in range(l):
        if s[i]=='0':
            s_ = s_+'1'
        else:
            s_ = s_+'0'
    S = ''
    for i in range(n):
        if i%2==0:
            S = S+s
        else:
            S = S+s_
    s = s[::-1]
    for i in range(l):
        if s[i]=='1':
            p_d[n] += pow(2,i,mod)
    if S<=X:
        p_d[n] += 1

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

Submission status: Wrong Answer

Solution code:
#divisors

import bisect

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

over_num = int(input())
X = int(input(),2)
divisors = make_divisors(over_num)

total_list = []
rep_times = []
for one in divisors:
    if one == over_num:
        continue
    quotient = over_num //one 
    if quotient % 2 ==  1:        
        bin_list = list()
        for i in range(2**one):
            bin_list += [(format(i,'0'+str(one)+'b'),format(2**one-i-1,'0'+str(one)+'b'))]
        for one_bit in bin_list:
            total_list.append((int((one_bit[0]+one_bit[1])*(quotient//2)+one_bit[0],2),2*one))
            
total_list = sorted(total_list,key=lambda x:x[0])
num_list = [one[0] for one in total_list]
rep_list = [one[1] for one in total_list]

ref_num = bisect.bisect_right(num_list, X)

print((2*over_num*(X-ref_num+1)+sum(rep_list[:ref_num]))%998244353)

Submission status: Wrong Answer

Solution code:

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

#print(yakusu_n)
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
		#print(num, X>=Y)
		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
		#print(n, ans, before)

print(ans)

Submission status: Wrong Answer

Solution code:
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)
    
for r in REP:
    score=-2*N+2*r

    for j in REP[::-1]:
        if j>r and j%r==0:
            score+=2*N-2*j
            break

    #print(r,score)

    XSTR=X[:r]

    kosuu=int(XSTR,2)

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

    ANS+=kosuu*score

print(ANS%mod)

Submission status: Wrong Answer

Solution code:
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)
    
for r in REP:
    score=-2*N+2*r

    for j in REP:
        if j>r and j%r==0:
            score+=2*N-2*j

    #print(r,score)

    XSTR=X[:r]

    kosuu=int(XSTR,2)

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

    ANS+=kosuu*score

print(ANS%mod)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


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

        k_cycles = 0
        ans = 0
        for k in range(1, N // 2):
            if N % k == 0 and (N / k) % 2 == 1:
                first_k_bit = int(X[:k], 2)
                k_cycle = first_k_bit + 1
                for i in range(k, N, k):
                    if int(X[i:i + k], 2) < first_k_bit:
                        break
                    elif int(X[i:i + k], 2) == first_k_bit:
                        continue
                    else:
                        k_cycle -= 1
                        break
                k_cycles += k_cycle
                ans += 2 * k * k_cycle

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

        print(ans % 998244353)


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

Submission status: Wrong Answer

Solution code:
Z = 998244353


def calc(N, X):
    nx = int(X, base=2)
    Q = 2 ** N
    k = Q % (2 * N)
    c = (Q - k) // (k + 1)
    m = [c * (k + 1) + k for k in range(k)]
    v = len([x for x in m if x <= nx])
    return (2 * N * (nx % Z + 1 - v) + k * v) % Z


N = int(input())
X = input()
print(calc(N, X))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
show_flg=True

def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret

        

n=I()
x=I()

def ch(k,n):
    y=k
    
    for i in range(1,10**2):
        if k%2==1:
            k=(k-1)//2
        else:
            k=k//2+2**(n-1)
        
        #show(i,k)
        
        if k==y:
            return i
    return 0

ch(3,3)
n=15
x=2**n+1

ko=[]
for i in range(1,x):
    if ch(i,n)!=2*n:
        show(bin(i+(1<<(n+0*1)))[3:],ch(i,n),i)
        ko.append(ch(i,n)//2)
print(Counter(ko).items())
    
show(n,x)
'''    
2^n+1=X*p(x)
x
2X+1
2(2X+1)+1 = 4X+2X+1
8X+4X+2X+1 = (8+4+2)X+1 = 2^4-1-1
(2^t-2)X+1 = 2*(2^(t-1)-1)X+1
    
'''

Submission status: Wrong Answer

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())
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)

Submission status: Wrong Answer

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())
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)
'''

Submission status: Wrong Answer

Solution code:
mod=998244353
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()
  return divisors
D=make_divisors(n)
for d in D:
  if d%2==0:
    continue
  else:
    k=n//d
    y=(2**n-2**k)//(2**k+1)
    ct=(int(x,2)-y)//(y+1)+1
    ans-=ct*2*(n-k)
print(ans%mod)

Submission status: Wrong Answer

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 x < (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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=998244353
input=lambda :sys.stdin.readline().rstrip()
def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if n%i==0:
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if S[-1]!=T[0] else S+T[1:]

def resolve():
    n=int(input())
    s=input()
    D=divisors(n)
    C={d:0 for d in D} # x以下の数字のうち、周期2dの個数
    for d in D:
        if (n//d)%2==0: continue # N/dがevenなら0個
        else:
            t=s[:d].replace('0','$').replace('1','0').replace('$','1')
            t=(s[:d]+t)*(n//d-1)+s[:d]
            C[d]=int(s[:d],2)+1-(s<t)
            C[d]%=MOD
    # ここでC[d]を、最小周期2dの個数に更新
    for d in D:
        for d1 in D:
            if (d%d1==0 and d!=d1):
                C[d]-=C[d1]
    ans=0
    for d in D:
        ans+=2*d*C[d]%MOD
    print(ans%MOD)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=998244353
input=lambda :sys.stdin.readline().rstrip()
def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if n%i==0:
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if S[-1]!=T[0] else S+T[1:]

def resolve():
    n=int(input())
    s=input()
    x=int(s,2)
    D=divisors(n)
    C={d:0 for d in D} # x以下の数字のうち、周期2dの個数
    for d in D:
        if (n//d)%2==0: continue # N/dがevenなら0個
        else:
            t=s[:d].replace('0','$').replace('1','0').replace('$','1')
            t=(s[:d]+t)*(n//d-1)+s[:d]
            C[d]=int(s[:d],2)+1-(s<t)
            C[d]%=MOD
    # ここでC[d]を、最小周期2dの個数に更新
    for d in D:
        for d1 in D:
            if (d%d1==0 and d!=d1):
                C[d]-=C[d1]
    ans=0
    for d in D:
        ans+=2*d*C[d]%MOD
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
MOD = 998244353

ans = 2*n
for i in range(n):
    if s[i] == "1":
        ans += (2*n) * pow(2, (n-i-1), MOD)
        ans %= MOD

for i in range(1, n + 1):
    if n % i == 0 and (n // i) % 2 == 1 and n != i:
        ans -= 2 * (n - i) * int(s[0:i], 2)
        #tmp = s[0:i]
        #tmp = ["0" if ((tmp[j%i] == "0" and (j//i) % 2 == 0) or (tmp[j%i] == "1" and (j//i) % 2 == 1)) else "1" for j in range(n)]
        #tmp = "".join(tmp)
        #if int(s) >= int(tmp):
        #    ans -= 2*(n - i)
        #ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
MOD = 998244353

ans = 2*n
for i in range(n):
    if s[i] == "1":
        ans += (2*n) * pow(2, (n-i-1), MOD)
        ans %= MOD

for i in range(1, n + 1):
    if n % i == 0 and (n // i) % 2 == 1 and n != i:
        ans -= 2 * (n - i) * int(s[0:i], 2)
        tmp = s[0:i]
        tmp = ["0" if ((tmp[j%i] == "0" and (j//i) % 2 == 0) or (tmp[j%i] == "1" and (j//i) % 2 == 1)) else "1" for j in range(n)]
        tmp = "".join(tmp)
        if int(s) >= int(tmp):
            ans -= 2*(n - i)
        ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
X = input()
x = int(X, 2)
mod = 998244353


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort(reverse=True)
    return array


ans = (2 * n * (x+1)) % mod
div_list = divisors(n)
div_n = []
done = set()
for div in div_list:
    l = n // div
    if l < 3:
        continue
    if div in done:
        continue
    if l % 2 == 1:
        div_n.append(div)
        done |= set(divisors(div))


for div in div_n:
    l = n // div
    if l < 3:
        break
    if l % 2 == 0:
        continue

    repeat = X[:div]
    reverse = 2**div-1 - int(repeat, 2)
    reverse = format(reverse, '0'+str(div)+'b')
    count = int(repeat, 2) + 1
    for i in range(1, l):
        if i % 2 == 1:
            compare = reverse
        else:
            compare = repeat

        check = X[div*i:div*(i+1)]
        if compare == check:
            continue
        elif compare > check:
            count -= 1
            break
        elif compare < check:
            break

    ans -= 2 * n * count
    ans += 2 * div * count
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
X = input()
x = int(X, 2)
mod = 998244353


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort()
    return array


ans = (2 * n * (x+1)) % mod
div_n = divisors(n)
for div in div_n:
    l = n // div
    if l < 3:
        break
    if l % 2 == 0:
        continue

    repeat = X[:div]
    reverse = 2**div-1 - int(repeat, 2)
    reverse = format(reverse, '0'+str(div)+'b')
    count = int(repeat, 2) + 1
    for i in range(1, l):
        if i % 2 == 1:
            compare = reverse
        else:
            compare = repeat

        check = X[div*i:div*(i+1)]
        if compare == check:
            continue
        elif compare > check:
            count -= 1
            break
        elif compare < check:
            break

    ans -= 2 * n * count
    ans += 2 * div * count
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
X = input()
x = int(X, 2)
mod = 998244353


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort()
    return array


ans = (2 * n * (x+1)) % mod
div_n = divisors(n)
for div in div_n:
    l = n // div
    if l < 3:
        break
    if l % 2 == 0:
        continue

    repeat = X[:div]
    reverse = 2**div - int(repeat, 2)
    reverse = format(reverse, '0'+str(div)+'b')
    count = int(repeat, 2) + 1
    for i in range(1, l):
        if i % 2 == 1:
            compare = reverse
        else:
            compare = repeat

        check = X[div*i:div*(i+1)]
        if compare == check:
            continue
        elif compare > check:
            break
        elif compare < check:
            count -= 1
            break

    ans -= (2*n - 2*div) * count
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
X = input()
x = int(X, 2)
mod = 998244353


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort()
    return array


ans = (2 * n * (x+1)) % mod
div_n = divisors(n)
for div in div_n:
    l = n // div
    if l < 3:
        break
    if l % 2 == 0:
        continue

    for i in range(2**div):
        repeat = i
        reverse = 2**div-i

        for j in range(l):
            if j % 2 == 0:
                compare = format(repeat, '0'+str(div)+'b')
            else:
                compare = format(reverse, '0'+str(div)+'b')
            if X[j*div:(j+1)*div] < compare:
                continue
            else:
                break
        else:
            break

        ans -= 2*n - 2*div

ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = int(input(),2)
MOD = 998244353
ans = ((X+1)%MOD) * 2*N
L = []
for i in range(1,N//3+1):
    if N%(2*i) == i:
        for j in range(2**i):
            b = int( (("0"*i+bin(j)[2:])[-i:] \
                   + ("0"*i+bin(2**i-j-1)[2:])[-i:])*(N//(2*i))\
                   + ("0"*i+bin(j)[2:])[-i:],2)
            if X >= b and not(b in L):
                L.append(b)
                ans -= 2*N
                ans += 2*i
                ans %= MOD
print(ans)