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

Solution (Python):
n = int(input())
X = input()
int_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


def is_repeatable(block):
    """
    分割したブロックの個数から、繰り返し可能か判定
    ブロック数は１以外の奇数の時に繰り返し可能
    :param block: 全体の長さnを等間隔に分割した時の、ブロック数
    :return: 繰り返し可能ならTrue そうでないならFalse
    """
    if block == 1:
        return False
    else:
        if block % 2 == 1:
            return True
        else:
            return False


def get_small_repeatable_list(length):
    """
    ブロックの長さを引数として受け取り、
    この長さを元にして、さらに小さい繰り返し配列が作成可能かどうかを確認し、
    小さく繰り返し配列のブロック長さをリストで返す
    （ダブルカウントのチェック）
    例　長さ6のブロックを繋いだ　6_6^_6　の配列の場合
    　　(2_2^_2)_(2^_2_2^)_(2_2^_2)の繰り返し配列が作成できる
    :param length: ブロックの長さ
    :return: ダブルカウントしてしまっているもののリスト
    """
    small_blocks = divisors(length)
    small_length_list = []
    for small_block in small_blocks:
        if is_repeatable(small_block):
            small_length = length//small_block
            small_length_list.append(small_length)

    return small_length_list


ans = (2 * n * (int_x+1)) % mod
div_list = divisors(n)

blocks = []
for div in div_list:
    block = div
    if is_repeatable(block):
        blocks.append(block)

blocks.sort(reverse=True)
done = {}
for block in blocks:
    length = n // block
    forward = X[:length]
    reverse = 2**length-1 - int(forward, 2)
    reverse = format(reverse, '0'+str(length)+'b')
    count = int(forward, 2) + 1
    for i in range(1, block):
        if i % 2 == 1:
            compare = reverse
        else:
            compare = forward

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

    small_repeatable_list = get_small_repeatable_list(length)
    for small_length in small_repeatable_list:
        double_count = done[small_length]
        count -= double_count

    done[length] = count
    ans -= 2*n*count
    ans += 2*length*count
    ans %= mod

print(ans)

Solution (Python):
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').zfill(num_len))*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)

Solution (Python):
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())
    x=input()
    y=''.join('1' if c=='0' else '0' for c in x) 
    D=divisors(N)
    C={d:0 for d in D} 
    for d in D:
        if (N//d)%2==0: continue 
        else:
            z=(x[:d]+y[:d])*((N//d-1)//2)+x[:d]
            C[d]=int(x[:d],2)+1-(x<z)
            C[d]%=MOD
    
    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()

Solution (Python):
def o_divisors(n):
    L = [i for i in range(1, int(n**0.5)+5) if n%i == 0]
    L += [n//i for i in L]
    L = sorted(list(set(L)))
    return [l for l in L if n//l % 2]
    
N = int(input())
T = input()
P = 998244353
bt = int(T, 2)
c = 0
ans = 0
L = []
for k in o_divisors(N):
    tt = T[:k]
    tt_ = tt.replace("0", "2").replace("1", "0").replace("2", "1")
    ttf = tt + (tt_ + tt) * ((N//k-1)//2)
    aa = int(tt, 2) + (int(ttf, 2) <= bt)
    for l, cc in L:
        if k % l == 0:
            aa -= cc
    L.append((k, aa))
    c += aa
    ans += k*2*aa
        
ans = (ans + 2 * N * (bt - c + 1)) % P
print(ans)

Solution (Python):
def o_divisors(n):
    L = [i for i in range(1, int(n**0.5)+5) if n%i == 0]
    L += [n//i for i in L]
    L = sorted(list(set(L)))
    return [l for l in L if n//l % 2]
    
N = int(input())
T = input()
P = 998244353
bt = int(T, 2)
c = 0
ans = 0
L = []
for k in o_divisors(N):
    tt = T[:k]
    tt_ = tt.replace("0", "2").replace("1", "0").replace("2", "1")
    ttf = tt + (tt_ + tt) * ((N//k-1)//2)
    aa = int(tt, 2) + (int(ttf, 2) <= bt)
    for l, cc in L:
        if k % l == 0:
            aa -= cc
    L.append((k, aa))
    c += aa
    ans += k*2*aa
        
ans = (ans + 2 * N * (bt - c + 1)) % P
print(ans)

Solution (Python):
def get_divisor(n):
    ret = []
    for i in range(3, n + 1, 2):
        if n % i == 0:
            ret.append(i)
    return ret


def get_dec(x, MOD):
    b = 1
    t = 0
    for c in x[::-1]:
        if c == '1':
            t = (t + b) % MOD
        b = b * 2 % MOD
    return t


def count_head_smaller(x, y, d, t, MOD):
    p = x[:t]
    q = y[:t]
    k = get_dec(p, MOD)
    r = (p + q) * (d // 2) + p
    if x >= r:
        k += 1
    return k


def solve(n, x):
    MOD = 998244353
    divisors = get_divisor(n)
    divisors.reverse()
    checked_divisors = {}

    y = ''.join('1' if c == '0' else '0' for c in x)

    ans = 0
    short = 0
    for d in divisors:
        t = n // d
        k = count_head_smaller(x, y, d, t, MOD)

        for pd, pk in checked_divisors.items():
            if pd % d != 0:
                continue
            k -= pk

        ans = (ans + 2 * t * k) % MOD
        short += k
        checked_divisors[d] = k

    t = (get_dec(x, MOD) + 1 - short) % MOD
    ans = (ans + t * 2 * n) % MOD
    return ans


n = int(input())
x = input()
print(solve(n, x))

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

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



def divisor_list(N): 
    if N == 1: return [1]
    res = []
    for i in range(1,N):
        if i*i >= N: break
        if N%i == 0:
            res.append(i)
            res.append(N//i)
    if i*i == N: res.append(i)
    return sorted(res)


div = divisor_list(n)

div = [i for i in div if i%2]


ans = []

MOD = 998244353
for i in div:
    per = n//i
    if i == 1:
        less = 0
        eq = 1
        for j in x:
            if j=="1":
                less *= 2
                less += eq
                less %= MOD
            else:
                less *= 2
                less %= MOD
        res = less+1
        
        ans.append(res)
    else:
        per = n//i
        less = 0
        eq = 1
        for j in x[:per]:
            if j=="1":
                less *= 2
                less += eq
                less %= MOD
            else:
                less *= 2
                less %= MOD
        res = less

        X = x[:per]
        Y = "".join(["1" if i=="0" else "0" for i in X])
        X = X+Y
        X = (X*i)[:n]
        if X <= x: res += 1
                
        
        ans.append(res)



for j in range(len(ans)-1,-1,-1):
    for k in range(j):
        if div[j]%div[k] == 0:
            ans[k] -= ans[j]

    
res = 0    
for d,a in zip(div,ans):
    res += a*(n//d)*2%MOD

print(res%MOD)

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

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


def main():
    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

        
            

        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)


if __name__ == '__main__':
    main()

Solution (Python):

"""
Created on Sat Oct  5 21:16:35 2019

@author: 23374
"""

from math import *
P = 998244353

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

a = []

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

b = a.copy()
b.reverse()
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 )

Solution (Python):
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 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
def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)
def o_divisors(N):
    return [a for a in divisors(N) if N//a % 2 and a < N]
    
N = int(input())
T = input()
P = 998244353
ods = o_divisors(N)

bt = int(T, 2)
c = 0
ans = 0
L = []
for k in ods:
    tt = T[:k]
    tt_ = tt.replace("0", "2").replace("1", "0").replace("2", "1")
    
    ttf = tt + (tt_ + tt) * ((N//k-1)//2)
    aa = int(tt, 2)
    if int(ttf, 2) <= bt:
        aa += 1
    for l, cc in L:
        if k % l == 0:
            aa -= cc
    L.append((k, aa))
    c += aa
    ans += k*2*aa
        
ans = (ans + 2 * N * (bt - c + 1)) % P
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

N = int(readline())
X = read().rstrip().decode('utf-8')

def F(d):
    """
    ・dは奇数
    ・d個のブロックに分けられるものの個数
    """
    L = N//d
    arr = [int(X[i:i+L],2) for i in range(0,N,L)]
    cnt = arr[0] 
    x = arr[0] 
    flip_x = ((1<<L)-1)^x
    bl = True
    for i,y in enumerate(arr):
        if i&1:
            if y > flip_x:
                break
            elif y == flip_x:
                continue
            else:
                bl = False
                break
        if y > x:
            break
        elif y == x:
            continue
        else:
            bl = False
            break
    return cnt + bl


div = set(x for x in range(1,1000) if N%x == 0)
div |= set(N//x for x in div)
div = sorted(d for d in div if d&1)

cnt = [F(d) for d in div]


D = len(div)
for n in range(D-1,-1,-1):
    for m,d in enumerate(div[:n]):
        if div[n]%d == 0:
            cnt[m] -= cnt[n]

answer = sum((N//x)*y for x,y in zip(div,cnt))*2
answer %= MOD
print(answer)