Submission #7871114

---

Source Code Expand

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 Info

Judge Result