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: Runtime Error

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

numX = int(X, 2)

if(N%2 == 1):
    ans = N*2*(numX+1)
    for i in range((N-3)//6):
        comp1 = ("1"*(2*i+1) + "0"*(2*i+1))*(N//(2*(2*i+1))  + "1"*(2*i+1)
        comp2 = ("0"*(2*i+1) + "1"*(2*i+1))*(N//(2*(2*i+1))  + "0"*(2*i+1)

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

else:
    ans = N*2*(numX+1)
    for i in range(N//6):
        comp1 = ("1"*(2*i) + "0"*(2*i))*(N//(4*i))  +"1"*(2*i)
        comp2 = ("0"*(2*i) + "1"*(2*i))*(N//(4*i))  +"0"*(2*i)

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


print(ans%998244353)

Submission status: Runtime Error

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

numX = int(X, 2)


if(N%2 == 1):
    ans = N*2*(numX+1)
    for i in range((N-3)//6):
        comp1 = ("1"*(2*i+1) + "0"*(2*i+1))*(N//(2*i))  +"1"*(2*i+1)
        comp2 = ("0"*(2*i+1) + "1"*(2*i+1))*(N//(2*i))  +"0"*(2*i+1)

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

else:
    ans = N*2*(numX+1)
    for i in range(N//6):
        comp1 = ("1"*(2*i) + "0"*(2*i))*(N//(2*i))  +"1"*(2*i)
        comp2 = ("0"*(2*i) + "1"*(2*i))*(N//(2*i))  +"0"*(2*i)

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


print(ans%998244353)

Submission status: Runtime Error

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

count=0
for k in range(2,X+1):
    k1=k
    if k%2==1:
        k=(k-1)/2
    else:
        k=k/2+2**(N-1)
    while True:
        if k==k1:
            break
        elif k%2==1:
            k=(k-1)/2
            count=count+1
        else:
            k=k/2+2**(N-1)
            count=count+1

print(count+998244353)

Submission status: Runtime Error

Solution code:
#import sys
#input = sys.stdin.readline
#import heapq
#from fractions import gcd
#from collections import defaultdict
#sys.setrecursionlimit(10**9)
#map(int,input().split())

def main():
    n=int(input())
    x=int(input(),2)
    ans=[0]*(x+1)
    tmp=0
    for i in range(x+1):
        if ans[i]!=0:
            continue
        else:
            cnt=0
            tmp=i
            li=[tmp]
            while True:
                if tmp%2:
                    tmp=(tmp-1)//2
                    li.append(tmp)
                    cnt+=1
                else:
                    tmp=(tmp//2)+(2**(n-1))
                    li.append(tmp)
                    cnt+=1
                if tmp==i:
                    for ii in li:
                        if ii<=x:
                            ans[ii]=cnt
                    break
    print(sum(ans)%998244353)





if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
INF=998244353
n=int(input())
s=input().rstrip()
nx=0
for i in range(n):
    if s[i]=='1':
        nx=(nx+2**(n-1-i))%INF
if n%3==0:
    if s[0]=='1':
        l=0
        while s[l]=='1':
            l+=1
            if l==n:
                break
        if l>n//3:
            ans=(2*n*(nx+1-n//3*2))%INF+(n//3*2)**2
            ans=ans%INF
            print(ans)
        else:
            check=False
            for i in range(l,l+n//3):
                if s[i]=='1':
                    check=True
            if check:
                ans=(2*n*(nx+1-n//3-l))%INF+(n//3*2)*(n//3+l)
                ans=ans%INF
                print(ans)
            else:
                check=True
                for i in range(l+n//3,l+n//3*2):
                    if s[i]=='0':
                        check=False
                if check:
                    ans=(2*n*(nx+1-n//3-l))%INF+(n//3*2)*(n//3+l)
                    ans=ans%INF
                    print(ans)
                else:
                    ans=(2*n*(nx+1-n//3-l+1))%INF+(n//3*2)*(n//3+l-1)
                    ans=ans%INF
                    print(ans)
    else:
        x=-1
        for i in range(n):
            if s[i]=='1':
                x=i
                break
        if x==-1:
            ans=2*n
            ans=ans%INF
            print(ans)
        check=True
        for i in range(x,x+n//3):
            if s[i]=='0':
                check=False
        if not check:
            ans=(2*n*(nx+1-n//3+x+1))%INF+(n//3*2)*(n//3-x-1)
            ans=ans%INF
            print(ans)
        check=False
        for i in range(x+n//3,x+n//3*2):
            if s[i]=='1':
                check=True
        if check:
            ans=(2*n*(nx+1-n//3+x))%INF+(n//3*2)*(n//3-x)
            ans=ans%INF
            print(ans)
        else:
            check=True
            for i in range(x+n//3*2,n):
                if s[i]=='0':
                    check=False
            if check:
                ans=(2*n*(nx+1-n//3+x))%INF+(n//3*2)*(n//3-x)
                ans=ans%INF
                print(ans)
            else:
                if check:
                ans=(2*n*(nx+1-n//3+x+1))%INF+(n//3*2)*(n//3-x-1)
                ans=ans%INF
                print(ans)
else:        
    ans=(2*n*(nx+1))%INF
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
#import heapq
#from fractions import gcd
#from collections import defaultdict
#sys.setrecursionlimit(10**9)
#map(int,input().split())

def main():
    n=int(input())
    x=int(input(),2)
    ans=[0]*(x+1)
    tmp=0
    for i in range(x+1):
        if ans[i]!=0:
            continue
        else:
            cnt=0
            tmp=i
            li=[tmp]
            while True:
                if tmp%2:
                    tmp=(tmp-1)//2
                    li.append(tmp)
                    cnt+=1
                else:
                    tmp=(tmp//2)+(2**(n-1))
                    li.append(tmp)
                    cnt+=1
                if tmp==i:
                    for ii in li:
                        if ii<=x:
                            ans[ii]=cnt
                    break
    print(sum(ans)%998244353)





if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

th = 2 ** (n - 1) * 2


def calc_1(tmp_k):
    return (tmp_k - 1) / 2


def calc_2(tmp_k):
    return tmp_k / 2 + 2 ** (n - 1)


known={}
def calc_count(tmp_k):
    known_value=known.get(tmp_k)
    if known_value:
        return known_value
    if tmp_k % 2 == 1:
        new_k = calc_1(tmp_k)
    else:
        new_k = calc_2(tmp_k)

    if new_k == k:
        return 1

    if tmp_k > new_k > calc_2(tmp_k):
        return False

    calc_result = calc_count(new_k)
    if calc_result:
        calc_result += 1
    return calc_result


result = 0

for k in range(x + 1):
    calc_result = calc_count(k)
    known[k]=calc_result
    if calc_result:
        result += calc_result

print(result % 998244353)

Submission status: Runtime Error

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 "1" 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: Runtime Error

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

ind_1 = _X.index("1") if "1" 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: Runtime Error

Solution code:
from math import gcd

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

# n = 100000
# print(n)
# print('1' * n)

# l = [2, 10, 42, 170, 682, 2730, 10922, 43690, 174762]
# l = [12, 204, 3276, 52428]
# l = [56, 3640]
# l = [240, 61680]
# l = [992]

# for i in l:
    # print(len(bin(i)), bin(i))

MOD = 998244353

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

mx = 0

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: Runtime Error

Solution code:
# import numpy as np
#
# n = int(input())
#
# m = np.zeros((n, n), dtype=np.bool)
#
# for i in range(n):
#     l = [int(s) for s in list(input())]
#     m[i]  =l
# a = np.count_nonzero(m,axis=0)
# r = np.count_nonzero(np.count_nonzero(m, axis=0) > 1)
# r = r or -1
# print(r)


n = int(input())
x = int(input(), 2)

th = 2 ** (n - 1) * 2


def calc_1(tmp_k):
    return (tmp_k - 1) / 2


def calc_2(tmp_k):
    return tmp_k / 2 + 2 ** (n - 1)


def calc_count(tmp_k):
    if tmp_k % 2 == 1:
        new_k = calc_1(tmp_k)
    else:
        new_k = calc_2(tmp_k)

    if new_k == k:
        return 1

    if tmp_k > new_k > calc_2(tmp_k):
        return False

    calc_result = calc_count(new_k)
    if calc_result:
        calc_result += 1
    return calc_result


result = 0

for k in range(x + 1):
    calc_result = calc_count(k)
    if calc_result:
        result += calc_result

print(result % 998244353)

Submission status: Runtime Error

Solution code:
N=int(input())
X=int(input(),2)
def op(k):
    if k%2==0:
        return k//2 + 2**(N-1)
    else:
        return (k-1)//2
def loop(k):
    if memo[k]!=-1:
        return memo[k]
    else:
        x=op(k)
        count=1
        L=[k,x]
        while(x!=k):
            if memo[x]!=-1:
                count=0
                if x in L:
                    L.remove(x)
                break
            x=op(x)
            L.append(x)
            count+=1
        
#         print(L)
        for l in L:
            memo[l]=count
        return memo[k]
ans=0
memo=[-1]*(2**15)
for i in range(X+1):
    ans+=loop(i)
print(ans)

Submission status: Runtime Error

Solution code:
def calc(num, n) :
    if (num % 2 == 0):
        return int((num + 2 ** n) / 2)
    else:
        return int((num - 1) / 2)

n = int(input())
x = int(input(), 2)

calc_list = []
for start in range(x+1):
    temp_val = start
    
    part_list = []
    while True:
        temp_val = calc(temp_val, n)
        part_list.append(temp_val)

        if (start == temp_val):
            break
        
        if (temp_val < start):
            if (start in calc_list[temp_val]):
                index = calc_list[temp_val].index(start)
                part_list.extend(calc_list[temp_val][0:index+1:])
                break
            else:
                part_list = []
                break
    
    calc_list.append(part_list)

operation_sum = 0
for each_list in calc_list:
    operation_sum += len(each_list)

print(operation_sum % 998244353)

Submission status: Runtime Error

Solution code:
MOD = 998244353


def dig(pos, depth, visited, graph):
    dest = graph[pos]
    if dest == pos:
        arr[pos] = 0
        arr[dest] = 0
    elif dest in visited.keys():
        res = depth - visited[dest] + 1
        for v in visited.keys():
            if visited[v] >= visited[dest]:
                arr[v] = res
    else:
        visited[dest] = depth+1
        dig(dest, depth+1, visited, graph)


num_pow = int(input())
range_upper = int(input(), base=2)

const = pow(2, num_pow-1)
calc_upper = max(pow(2, num_pow), range_upper)

arr = [None] * (calc_upper+1)
graph_dict = {i: i//2 + const*((i+1) % 2) for i in range(0, calc_upper+1)}

for i in range(0, range_upper+1):
    if arr[i] is not None:
        continue
    else:
        arr[i] = 0
        dig(i, 0, {i: 0}, graph_dict)

# print(list(graph_dict.items())[:40])
# print(arr[:2000])
print(sum([x for x in arr[:range_upper+1] if x is not None]) % MOD)

Submission status: Runtime Error

Solution code:
import sys

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


def proc(x):
    if x % 2 == 1:
        return int((x - 1) / 2)
    else:
        return int(x / 2 + 2 ** (N - 1))


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
        elif num_calc == MAX_TRY - 1:
            print('-1')
            sys.exit(0)

print(total % 998244353)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

N, X = int(input()), int(input(), 2)
count = 0
C = 2**(N-1)

@lru_cache(maxsize=None)
def func(k):
    return (k-1)/2 if k%2 == 1 else k/2+C

for k in range(X + 1):
    i = 0
    k_ = k
    while(True):
        k_ = func(k_)
        i+=1
        if k == k_:
            break
    count += i
print(count)