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: Accepted

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=list(X[:u])
    for i in range(u):
        if y[i]=="0":
            y.append("1")
        else:
            y.append("0")
    y="".join(y)
    y*=(U+1)//2
    y=y[:n]
    if y<=X:
        cnt+=1
    for i in range(len(s)):
        if u%s[i]==0:
            cnt-=t[i]
    sum=(sum+(2*cnt*u)%mod)%mod
    s.append(u)
    t.append(cnt)
    count=(count+cnt)%mod
print((((num+1-count)*2*n)%mod+sum)%mod)

Submission status: Accepted

Solution code:
import math
import os
import sys
from collections import defaultdict

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

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

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


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


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

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


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


# @debug
def count(d):
    sz = N // d

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


# 全部 N * 2 で戻る
counts = defaultdict(int)
counts[N * 2] = int(X, 2) + 1

# k 回でもとに戻る
ks = [N * 2 // d for d in get_divisors(N) if d % 2 and d != 1]
for k in ks:
    d = N * 2 // k
    counts[k] = count(d)

# 数え上げ
# k の約数はカウント済みなので引く
ans_counts = defaultdict(int)
for k in sorted(ks):
    ans_counts[k] = counts[k] - sum([ans_counts[d] for d in get_divisors(k)])
ans_counts[N * 2] = counts[N * 2] - sum([ans_counts[d] for d in get_divisors(N * 2)])

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

main()

Submission status: Accepted

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

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

p_d = {}

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

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

Submission status: Accepted

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]
    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: Accepted

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

# 約数包除で重複を除く
for i in range(1, n + 1):
    for j in range(2*i, n + 1, i):
        if n % j == 0:
            a[j] -= a[i]

# b:有効周期
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: Accepted

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

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

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

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


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

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

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

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

D[N] = Y - cnt + 1

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

print(ans)

Submission status: Accepted

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)

from collections import defaultdict
score=defaultdict(int)

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

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

    #print(r,score)

    XSTR=X[:r]

    kosuu=int(XSTR,2)

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

    ANS+=kosuu*sc

print(ANS%mod)

Submission status: Accepted

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

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

  divisors.sort(reverse=True)
  return divisors
D=make_divisors(n)
CT=collections.defaultdict(int)
for d in D:
  if d%2==0 or d==1:
    continue
  else:
    k=n//d
    #下から0がk個、1がk個、、、、を繰り返す数を求める、ｙとする。
    #その周期は2*k
    y=(2**n-2**k)//(2**k+1)

    #ｙ+（ｙ＋１）*yyも同じ周期をもつ
    #x以下の個数を数える
    ct=(int(x,2)-y)//(y+1)+1
    #重複分を差し引く
    Dk=make_divisors(k)
    for dk in Dk:
      if dk<k:
        ct-=CT[dk]
    CT[k]=ct

    #ansはすべてを2nで数えているのでそこから2(n-k)を引く
    ans-=ct*2*(n-k)


print(ans%mod)

Submission status: Accepted

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 Tc*(N//d)+Tc[:N-d*(N//d)] <= X:
        count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

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

print(ans)

Submission status: Accepted

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: Accepted

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)

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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())
    x=input()
    y=''.join('1' if c=='0' else '0' for c in x) # xのbit反転
    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:
            z=(x[:d]+y[:d])*((N//d-1)//2)+x[:d]
            C[d]=int(x[:d],2)+1-(x<z)
            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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

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

# N のすべての正の約数を求める
# O(sqrt(N))
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
        #print(less,eq)
        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 -= res*(2*(n-per))%MOD
        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)

Submission status: Accepted

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
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 )

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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] # 最初の桁がちょうどx。満たすか確認する。
    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)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

x=int(x,2)
num=list(range(x+1))

ans=[]
for i in num:
    if i>2**n:
        break
    count=0
    temp=i

    while True:
        if temp%2!=0:
            temp=(temp-1)/2
            count+=1
            if temp==i:
                ans.append(count)
                break
        if temp%2==0:
            temp=temp/2+2**(n-1)
            count+=1
            if temp==i:
                ans.append(count)
                break
print(sum(ans))

Submission status: Runtime Error

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 Tc*(N//d)+Tc[:N-d*(N//d)] <= X:
    #    count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

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

print(ans)