91 lines
No EOL
2.1 KiB
Python
91 lines
No EOL
2.1 KiB
Python
import sys
|
|
|
|
input_data = sys.stdin.read().split()
|
|
if not input_data:
|
|
sys.exit()
|
|
|
|
MOD = 998244353
|
|
G = 3
|
|
|
|
def ntt(a, invert):
|
|
n = len(a)
|
|
j = 0
|
|
for i in range(1, n):
|
|
bit = n >> 1
|
|
while j & bit:
|
|
j ^= bit
|
|
bit >>= 1
|
|
j ^= bit
|
|
if i < j:
|
|
a[i], a[j] = a[j], a[i]
|
|
step = 2
|
|
while step <= n:
|
|
half = step >> 1
|
|
wlen = pow(G, (MOD - 1) // step, MOD)
|
|
if invert:
|
|
wlen = pow(wlen, MOD - 2, MOD)
|
|
w = [1] * half
|
|
curr = 1
|
|
for i in range(half):
|
|
w[i] = curr
|
|
curr = (curr * wlen) % MOD
|
|
for i in range(0, n, step):
|
|
for j in range(half):
|
|
u = a[i + j]
|
|
v = (a[i + j + half] * w[j]) % MOD
|
|
a[i + j] = (u + v) % MOD
|
|
a[i + j + half] = (u - v + MOD) % MOD
|
|
step <<= 1
|
|
if invert:
|
|
n_inv = pow(n, MOD - 2, MOD)
|
|
for i in range(n):
|
|
a[i] = (a[i] * n_inv) % MOD
|
|
|
|
def multiply(a, b):
|
|
if not a or not b:
|
|
return []
|
|
sz = len(a) + len(b) - 1
|
|
n = 1
|
|
while n < sz:
|
|
n <<= 1
|
|
a = a + [0] * (n - len(a))
|
|
b = b + [0] * (n - len(b))
|
|
ntt(a, False)
|
|
ntt(b, False)
|
|
for i in range(n):
|
|
a[i] = (a[i] * b[i]) % MOD
|
|
ntt(a, True)
|
|
return a[:sz]
|
|
t = int(input_data[0])
|
|
ptr = 1
|
|
for _ in range(t):
|
|
if ptr >= len(input_data):
|
|
break
|
|
n = int(input_data[ptr])
|
|
s = input_data[ptr+1]
|
|
ptr += 2
|
|
A = [0] * n
|
|
B = [0] * n
|
|
for i in range(n):
|
|
if s[i] == 'V':
|
|
A[i] = 1
|
|
elif s[i] == 'K':
|
|
B[n - 1 - i] = 1
|
|
C = multiply(A, B)
|
|
bad = [False] * (n + 1)
|
|
for k in range(len(C)):
|
|
if C[k] > 0:
|
|
dist = abs(n - 1 - k)
|
|
if dist <= n:
|
|
bad[dist] = True
|
|
ans = []
|
|
for p in range(1, n + 1):
|
|
valid = True
|
|
for m in range(p, n + 1, p):
|
|
if bad[m]:
|
|
valid = False
|
|
break
|
|
if valid:
|
|
ans.append(p)
|
|
print(len(ans))
|
|
print(*(ans)) |