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:
if __name__ == "__main__":
    n = int(input())
    x = input()
    x_num = int(x, 2)

    is_corner = [False] * (n // 3 + 1)
    for i in range(1, n // 3 + 1):
        if n % i == 0 and (n // i) % 2 == 1:
            is_corner[i] = True
    # print(is_corner)
    corner_num = {}

    for index, is_c in enumerate(is_corner):
        if is_c:
            corner_num[index * 2] = []
            pattern_len = index
            temp1 = ""
            temp2 = ""
            pattern_count = 0
            is_zero = False
            for _ in range(n):
                if pattern_count >= pattern_len:
                    pattern_count = 0
                    if is_zero:
                        is_zero = False
                    else:
                        is_zero = True
                if is_zero:
                    temp1 = temp1 + "1"
                else:
                    temp1 = temp1 + "0"

                pattern_count += 1

            corner_num[index * 2].append(int(temp1, 2))
            for i in range(1, pattern_len * 2):
                corner_num[index * 2].append(int(temp1[-i:] + temp1[:-i], 2))

    corner_num_len = 0
    corner_num_sum = 0
    for corner in corner_num.items():
        num1 = len(list(filter(lambda xl: xl <= x_num, corner[1])))
        print(len(corner[1]))
        print(num1)
        num1 = len(corner[1])
        corner_num_len += num1
        corner_num_sum += num1 * corner[0]
    print(corner_num_sum)
    print((2 * n * (x_num + 1 - corner_num_len) % 998244353 + corner_num_sum) % 998244353)
    # print(corner_num)
    # print(corner_num_len)

# 奇数の場合　0埋めの右1シフト 1の桁が1つ減る操作
# 偶数の場合　1埋めの右1シフト 1の桁が1つ増える操作
# 一番右の桁を反転させて左に付けている→高々2N回操作すれば戻ってくる
# 2N回より短い回数で戻ってくる数は？
# 奇数桁であり、0,1が交互になっている数は2回の操作で戻ってくる

# 6桁の場合
# 0 -> 32 -> 48 -> 56 -> 60 -> 62 -> 63 -> 31 -> 15 -> 7 -> 3 -> 1 -> 0
# 2 -> 33 -> 16 -> 40 -> 52 -> 58 -> 61 -> 30 -> 47 -> 23 -> 11 -> 5 -> 2
# 4 -> 34 -> 49 -> 24 -> 44 -> 54 -> 59 -> 29 -> 14 -> 39 -> 19 -> 9 -> 4
# 6 -> 35 -> 17 -> 8 -> 36 -> 50 -> 57 -> 28 -> 46 -> 55 -> 27 -> 13 -> 6
# 10 -> 37 -> 18 -> 41 -> 20 -> 42 -> 53 -> 26 -> 45 -> 22 -> 43 -> 21 -> 10
# 12 -> 38 -> 51 -> 25 -> 12
# 001100, 100110, 110011, 011001
# 010 -> 2　1で割ったら奇数になる場合に存在する
# 001100 -> 4　2で割ったら奇数になる場合に存在する
# 000111000 -> 6　3で割ったら奇数になる場合に存在する
# 4で割ったら… n//3まで確認すれば十分

# 5桁の場合
# 0 -> 16 -> 24 -> 28 -> 30 -> 31 -> 15 -> 7 -> 3 -> 1 -> 0
# 2 -> 17 -> 8 -> 20 -> 26 -> 29 -> 14 -> 23 -> 11 -> 5 -> 2
# 4 -> 18 -> 25 -> 12 -> 22 -> 27 -> 13 -> 6 -> 19 -> 9 -> 4
# 10 -> 21 -> 10

# 4桁の場合
# 0 -> 8 -> 12 -> 14 -> 15 -> 7 -> 3 -> 1 -> 0
# 2 -> 9 -> 4 -> 10 -> 13 -> 6 -> 11 -> 5 -> 2

# 3桁の場合
# 0 -> 4 -> 6 -> 7 -> 3 -> 1 -> 0
# 2 -> 5 -> 2

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
X = input()

def find_prime_odd_dv(N):
  L=[]
  while N%2 ==0:
    N = N//2
  N_org = N
  for i in range(3,int(np.sqrt(N))+1,2):
    if i>N:
      break
    while N%i == 0:
      L.append(i)
      N = N//i
  if N!=1:
    L.append(N)
  return L

def find_odd_dv(L):
  div = set()
  len_L=len(L)
  for i in range(len_L):
    s=L[0]
    div.add(s)
    L2=find_odd_dv(L[1:])
    for elem in L2:
      div.add(elem)
      div.add(s*elem)
  div_L = list(div)
  return div_L

L=find_prime_odd_dv(N)
odd_div=find_odd_dv(L)

total=0
exc=0
for div in odd_div:
  cycle = N//div
  small_str = ''
  large_str = ''
  flag=0
  for i in range(div):
    if flag==0:
      add_str = '0'*cycle
    else:
      add_str = '1'*cycle
    small_str = small_str+add_str
    flag = 1-flag
    
  flag=1
  for i in range(div):
    if flag==0:
      add_str = '0'*cycle
    else:
      add_str = '1'*cycle
    large_str = large_str+add_str
    flag = 1-flag
  #print(small_str)
  #print(large_str)
  if X>=small_str:
    #print(small_str)
    exc += 1
    total += cycle*2
  if X>=large_str:
    #print(large_str)
    exc += 1
    total += cycle*2
#print(total)
ordinary = int(X,2)-exc+1
total += 2*N*ordinary
divid=998244353
print(total%divid)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
MOD = 10**9 + 7

# 基本的には 2*n の移動が必要

# いい感じのときはそれが必要ない
# 例 n=3 ['010', '101', '010']
# 2回でおっけー
# 例 n=6 ['110011', '011001', '001100', '100110', '110011']
# 4回でおっけー
# このような場合をうまく数える必要がある。

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*i)*(2*n - i*2)
        ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
X = input()

def find_prime_odd_dv(N):
  L=[]
  while N%2 ==0:
    N = N//2
  N_org = N
  for i in range(3,int(np.sqrt(N))+1,2):
    if i>N:
      break
    while N%i == 0:
      L.append(i)
      N = N//i
  if N!=1:
    L.append(N)
  return L

def find_odd_dv(L):
  div = set()
  len_L=len(L)
  for i in range(len_L):
    s=L[0]
    div.add(s)
    L2=find_odd_dv(L[1:])
    for elem in L2:
      div.add(elem)
      div.add(s*elem)
  div_L = list(div)
  return div_L

L=find_prime_odd_dv(N)
odd_div=find_odd_dv(L)

total=0
exc=0
for div in odd_div:
  cycle = N//div
  small_str = ''
  large_str = ''
  flag=0
  for i in range(div):
    if flag==0:
      add_str = '0'*cycle
    else:
      add_str = '1'*cycle
    small_str = small_str+add_str
    flag = 1-flag
    
  flag=1
  for i in range(div):
    if flag==0:
      add_str = '0'*cycle
    else:
      add_str = '1'*cycle
    large_str = large_str+add_str
    flag = 1-flag
  #print(small_str)
  #print(large_str)
  if X>=small_str:
    print(small_str)
    exc += 1
    total += cycle*2
  if X>=large_str:
    print(large_str)
    exc += 1
    total += cycle*2
print(total)
ordinary = int(X,2)-exc+1
total += 2*N*ordinary
divid=998244353
print(total%divid)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=list(map(int,list(input())))
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
ans=0
count=0
i=0
count_0=0
while i<n:
    if x[i]==0:
        count_0+=1
        i+=1
    else:
        break
lst=[0]*(n+1)
for i in range(1,n):
    if n%i==0:
        if (n//i)%2==1:
            lst[i]=1
for i in range(count_0,n+1):
    if lst[i]==1:
        ans+=i*2
        count+=1
if count_0==0:
    count_1=0
    i=0
    while i<n:
        if x[i]==1:
            count_1+=1
            i+=1
        else:
            break
    for i in range(1,count_1+1):
        if lst[i]==1:
            ans+=i*2
            count+=1
print(ans+2*n*(num-count+1))

Submission status: Wrong Answer

Solution code:
N = int(input())
X = list(str(input()))
mod = 998244353
XN = 0
for i in range(N):
    if X[i] == "1":
        XN+=2**(N-i-1)
XN%=mod

n = 2*N
M = 2*(2**(N-1)-1)
if M%3 == 0:
    K = M//3
else:
    K = -1
    
if K == -1:
    ans = n*(XN+1)
    print(ans%mod)
else:
    kou = (XN+1)//(K+1)
    ans = n*(XN+1-kou) + kou*2
    #print(kou)
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = list(str(input()))
mod = 998244353
XN = 0
for i in range(N):
    if X[i] == "1":
        XN+=2**(N-i-1)

n = 2*N
M = 2*(2**(N-1)-1)
if M%3 == 0:
    K = M//3
else:
    K = -1
    
if K == -1:
    ans = n*(XN+1)
    print(ans%mod)
else:
    kou = (XN+1)//(K+1)
    ans = n*(XN+1-kou) + kou*2
    #print(kou)
    print(ans%mod)

Submission status: Wrong Answer

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

numX = int(X, 2)


if(N%2 == 1):
    comp1 = "10"*(N//2)+"1"
    comp2 = "01"*(N//2)+"0"

    if(int(X)-int(comp1))>0:
        ans = N*2*(numX+1-2) + 2 * 2
    elif(int(X)-int(comp2))>0:
        ans = N*2*(numX+1-1) + 2 * 1
    else:
        ans = N*2*(numX+1)

else:
    comp1 = "1100"*(N//4)+"11"
    comp2 = "0011"*(N//4)+"00"
    if(int(X)-int(comp1))>0:
        ans = N*2*(numX+1-4) + 4 * 4
    elif(int(X)-int(comp2))>0:
        ans = N*2*(numX+1-2) + 4 * 2
    else:
        ans = N*2*(numX+1)

print(ans%998244353)

Submission status: Wrong Answer

Solution code:
N = int(input())
_X = input()
X = int(_X,2)

ind_1 = _X.index("1") if "1" in _X else N
ind_0 = _X.index("0") if "0" in _X else N



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

    # divisors.sort()
    return divisors

result = ((X+1)*2*N )% 998244353
result

for n in make_divisors(N):
    str_010 = ("0"*(N//n)+"1"*(N//n) )*(n//2)+"0"*(N//n)
    for i in range((N//n)*2):
        if int(str_010,2) <= X:
            if ind_1 < ind_0:
                #print("1","1"*(ind_1+1) + str_010[:-ind_1-1])
                if int("1"*(ind_1+1) + str_010[:-ind_1-1],2) <= X:
                    result -= N*2
                    result += (N//n)*2
                
                result -= N*2*(ind_1+N//2)
                result += (N//n)*2 * (ind_1+N//2)
            else:
                #print("2",str_010[N//n-ind_1:] + "1"*(N//n-ind_1),N,n,ind_1,N//n-ind_1)
                if int(str_010[N//n-ind_1:] + "1"*(N//n-ind_1),2) <= X:
                    #print("yes!")
                    result -= N*2
                    result += (N//n)*2
                
                result -= N*2 * (N//n-ind_1 )
                result += (N//n)*2 *(N//n-ind_1 ) 
                
            break

print(result % 998244353)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

def lcm(i, j):
    return i * j // gcd(i, j)

MOD = 998244353

n = int(input())
s = input()
p = int(s, 2)


w = 1
cnt = p + 1
res = 0
done = []
while w * 3 <= n:
    if (n - w) % (w * 2) == 0:
        k = (n - w) // (w * 2)
        fir = int(('1' * w + '0' * w) * k, 2) + 1
        m = (p + 1) // fir
        q = 0
        for i in done:
            # 被り
            if fir % i == 0:
                m = 0
                break
            else:
                if q == 0:
                    q = lcm(i, fir)
                else:
                    q = lcm(q, lcm(i, fir))
        if q != 0:
            m -= (p + 1) // q
        if m == 0:
            w += 1
            continue
        done.append(fir)
        res += m * 2 * w
        res %= MOD
        cnt -= m
        # print(k, w, fir, m)
    w += 1
print((res + cnt * 2 * n) % MOD)
# print(len(done))

Submission status: Wrong Answer

Solution code:
import sys

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


def proc(x):
    if x % 2 == 1:
        return x >> 1
    else:
        return (x >> 1) + int('1'+'0'*(N-1), 2)

total = 0
MAX_TRY = 1000
for k in range(X + 1):
    p = k
    for num_calc in range(1, MAX_TRY):
        p = proc(p)
        if p == k:
            total += num_calc
            break

print(total % 998244353)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = int(input(),2)

counted = [0]*(N+1)

ans = 0
for i in range(1,N+1):
    if (not N%i) and (N//i)%2:
        temp = (X>>(N-i)) + 1
        for j in range(1,i):
            if not i%j:
                temp -= counted[j]
        
        #print(i,X>>(N-i),temp, N//i, ans)
        ans += temp * i * 2
        ans %= 998244353
        counted[i] = temp
        #print(ans)


print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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


def proc(x):
    if x % 2 == 1:
        return x >> 1
    else:
        return (x >> 1) + int('1'+'0'*(N-1), 2)

total = 0
MAX_TRY = 1000
for k in range(X + 1):
    p = k
    for num_calc in range(1, MAX_TRY):
        p = proc(p)
        if p == k:
            total += num_calc
            break
        if num_calc == MAX_TRY - 1:
            print('-1')
            sys.exit(0)

print(total % 998244353)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
x_10=int(x,2)
cnt=x_10+1
ans=0
n_copy=n
for i in range(3,n+1,2):
  if n%i==0:
    p=int(x[0:n//i],2)
    if x_10>=sum(p<<((n//i)*j) for j in range(0,i,2))+sum((2**(n//i)-p-1)<<((n//i)*j) for j in range(1,i,2)):
      cnt-=p+1
      ans+=(p+1)*2*(n//i)
    else:
      cnt-=p
      ans+=p*2*(n//i)
ans+=n*2*cnt
print(ans%998244353)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(str(input()))
c1 = "0"
c2 = []
for i in s:
    if c1 == "0":
        c1 = i
        continue
    else:
        c2.append(i)

c3 = ["1"]
for i in c2:
    c3.append(i)
c4 = "".join(c3)
c5 = int(c4, 2)


def func1(a):
    s1 = a%2
    if s1 == 1:
        return (a-1)//2
    else:
        return (a//2) + 2**(n-1)

b2 = {}
c2 = set()
for i in range(0, c5+1):
    boo = False
    count = 0
    i_base = i
    b = {}
    c = set()
    if i in c2:
        continue
    while boo == False:
        if i in c:
            for j in b.keys():
                if j <= c5:
                    b2[j] = count
                c2.add(j)
            boo = True
        elif i in c2:
            boo = True
        else:
            c.add(i)
            b[i] = count
            i = func1(i)
            count += 1

ans = sum(b2.values())
print(ans%998244353)

Submission status: Wrong Answer

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

numX = int(X, 2)


if(N%2 == 1):
    comp1 = "10"*(N//2)+"1"
    comp2 = "01"*(N//2)+"0"

    if(int(X)-int(comp1))>0:
        ans = N*2*(numX+1-2) + 2 * 2
    elif(int(X)-int(comp2))>0:
        ans = N*2*(numX+1-1) + 2 * 1
    else:
        ans = N*2*(numX+1)

else:
    ans = N*2*(numX+1)
    
print(ans%998244353)

Submission status: Wrong Answer

Solution code:
from math import *
P = 998244353

fin = input

n = int(fin())
num = int(fin(),2) + 1

a = []

for i in range(2,int(sqrt(2*n))+1):
    if 2*n%i==0 :
        a.append(i)

b = a.copy()
for x in b:
    if(x*x!=2*n):
        a.append(2*n//x)

def expgcd(x,x1,y,y1):
    if x<y :
        x, x1, y, y1 = y, y1, x, x1
    if y==0 :
        return (x,x1) if y1==-1 else (0,0)
    if y1==-1:
        return expgcd(x%y,x1,y,y1)
    else:
        c = -x1 if (x // y) % 2 == 1 else x1
        return expgcd(x%y,c,y,y1)

f = []
for k in a:
    x = expgcd(k,-1,n,1)
    f.append(0 if x == (0,0) else 2**x[0] + x[1])

Mnum = num % P
ans = Mnum * 2*n % P
g = [0] * len(a)
for i in range(len(a)):
    if (f[i]==0): continue
    x, y = a[i], num // ( (2**n+1) // f[i])
    for j in range(i):
        if (a[i]%a[j]==0) :
            y -= g[j]
    g[i] = y
    ans = (ans - y * (2*n - a[i]) ) % P

print( (ans+P) % P )

Submission status: Wrong Answer

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

numX = int(X, 2)

if(N%2 == 1):
    comp1 = "10"*(N//2)+"1"
    comp2 = "01"*(N//2)+"0"
else:
    comp1 = "10"*(N//2)
    comp2 = "01"*(N//2)

if(int(X)-int(comp1))>0:
    ans = N*2*(numX+1-2) + 2 * 2
elif(int(X)-int(comp2))>0:
    ans = N*2*(numX+1-1) + 2 * 1
else:
    ans = N*2*(numX+1)

print(ans%998244353)

Submission status: Wrong Answer

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

numX = 0
para = 1
for i in range(N):
    numX += int(X[N-1-i]) * para
    para *= 2

i = 0
while(True):
    if(X[i] == 1):
        break
    elif(i == N-1):
        break
    else:
        i += 1

if(N%2 == 1):
    comp1 = "10"*(N//2)+"1"
    comp2 = "01"*(N//2)+"0"
else:
    comp1 = "10"*(N//2)
    comp2 = "01"*(N//2)

if(int(X)-int(comp1))>0:
    ans = N*2*(numX+1-2) + 2 * 2
elif(int(X)-int(comp2))>0:
    ans = N*2*(numX+1-1) + 2 * 1
else:
    ans = N*2*(numX+1)

print(ans%998244353)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = int(input(),2)

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

    # divisors.sort()
    return divisors

result = ((X+1)*2*N )% 998244353
result

for n in make_divisors(N):
    str_010 = ("0"*(N//n)+"1"*(N//n) )*(n//2)+"0"*(N//n)
    for i in range((N//n)*2):
        if int(str_010,2) <= X:
            #print(str_010)
            result -= N*2
            result += (N//n)*2
            str_010 = str_010[1:] + str((1+int(str_010[0]))%2) 
        else:
            break

print(result % 998244353)

Submission status: Wrong Answer

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

    # divisors.sort()
    return divisors
  
result = ((X+1)*2*N )% 998244353
for n in make_divisors(N):
    str_010 = ("0"*(N//n)+"1"*(N//n) )*(n//2)+"0"*(N//n)
    for i in range((N//n)*2):
        if int(str_010,2) <= X:
            #print(str_010)
            result -= N*2
            result += (N//n)*2
        str_010 = str((1+int(str_010[-1]))%2) + str_010[:-1]
print(result % 998244353)

Submission status: Wrong Answer

Solution code:
import sys
s=input()
k=int(input())
count=1
answer=0
lastChange=False
roopContinue=False
lastWord=""
for i in range(len(s)):
  if i==len(s)-1 or k==1:
    print(len(s)*k//2)
    sys.exit()
  elif k==1:
    break
  elif s[i+1]==s[0]:
    lastWord+=s[0]
  else:
    break
s+=lastWord
for i in range(len(s)-1):
  if s[i]==s[i+1]:
    count+=1
    if i==len(s)-2:
      answer+=(count//2)
  else:
    answer+=(count//2)
    count=1
    if i==len(s)-2:
      answer+=(count//2)
print(answer*k)

Submission status: Time Limit Exceeded

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

print(ans % mod)

Submission status: Time Limit Exceeded

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
    for i in range(n // D[k]):
        m <<= D[k]
        if i % 2:
            m |= r_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]
            cnt[kk]%=mod
    ans %= mod

print(ans % mod)

Submission status: Time Limit Exceeded

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
    for i in range(n // D[k]):
        m <<= D[k]
        if i % 2:
            m |= r_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: Time Limit Exceeded

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 |= (2 ** D[k] - 1) ^ 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: Time Limit Exceeded

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 and n // i % 2:
        D += [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 |= (2 ** D[k] - 1) ^ 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: Time Limit Exceeded

Solution code:
def divisors(M):#Mの約数列 O(n^(0.5+e))
    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)

Submission status: Time Limit Exceeded

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 + (int(a, 2) >= int(k, 2))
    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)

Submission status: Time Limit Exceeded

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
    y=X[:u]
    for i in range(u):
        if X[i]=="0":
            y+="1"
        else:
            y+="0"
    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)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


# https://atcoder.jp/contests/agc039/submissions/7878237
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


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