Contest Duration: - (local time) (300 minutes) Back to Home

Submission #20639012

Source Code Expand

Copy
```import sys
import numpy as np
import numba
from numba import njit, b1, i1, i4, i8, f8

BACKET = 256
MOD = 1_000_000_007

@njit
def mpow(a, n):
p = 1
while n:
if n & 1:
p = p * a % MOD
a = a * a % MOD
n >>= 1
return p

@njit
def fact_table(N=1 << 20):
N += 1
fact = np.empty(N, np.int64)
fact[0] = 1
for n in range(1, N):
fact[n] = n * fact[n - 1] % MOD
fact_inv = np.empty(N, np.int64)
fact_inv[N - 1] = mpow(fact[N - 1], MOD - 2)
for n in range(N - 1, 0, -1):
fact_inv[n - 1] = fact_inv[n] * n % MOD
inv = np.empty(N, np.int64)
inv[0] = 0
inv[1:] = fact[:-1] * fact_inv[1:] % MOD
return fact, fact_inv, inv

@njit
def prime_table(N):
N += 1
is_prime = np.zeros(N, np.int64)
is_prime[2:3] = 1
is_prime[3::2] = 1
for p in range(3, N, 2):
if p * p >= N:
break
if is_prime[p]:
is_prime[p * p::p + p] = 0
return is_prime, np.where(is_prime)[0]

@njit
def to_integer_query(N, XY):
XY = XY - 1
P = np.arange(N)
change = np.zeros(N, np.bool_)
data = np.full((N, 5), -1, np.int64)
Q = len(XY)
q = 0

query = np.zeros((3 * len(XY), 2), np.int64)

def compress():
nonlocal P, change, data
"""
O(N) かけてよい
A：行き先が変更される可能性のあるインデックス
"""
data[:] = -1
for a in range(N):
if not change[a]:
continue
if data[a, 0] != -1:
continue
data[a] = (a, a, 1, a, 1)
v = a
while P[v] != a:
data[a, 4] += 1
if change[v] or change[P[v]]:
v = P[v]
data[v] = (v, v, 1, a, -1)
else:
v = P[v]
if P[v] == a:
break

def update_from(a):
nonlocal P, change, data
data[a] = (a, a, 1, a, 1)
v = a
while True:
v = P[data[v, 1]]
if v == a:
break
data[v, 3] = a
data[a, 4] += data[v, 2]

def swap(a, b):
nonlocal P, change, data, query, q
P[a], P[b] = P[b], P[a]
ra, rb = data[a, 3], data[b, 3]
same = ra == rb
if same:
query[3 * q + 0] = (-1, data[ra, 4])
update_from(a)
update_from(b)
query[3 * q + 1] = (1, data[a, 4])
query[3 * q + 2] = (1, data[b, 4])
else:
query[3 * q + 0] = (-1, data[ra, 4])
query[3 * q + 1] = (-1, data[rb, 4])
update_from(a)
query[3 * q + 2] = (1, data[a, 4])

for q in range(Q):
if q % BACKET == 0:
change[:] = 0
for i in range(q, min(Q, q + BACKET)):
x, y = XY[i]
change[x] = change[y] = 1
compress()
x, y = XY[q]
swap(x, y)
return query

@njit((i8, i8[:, :]), cache=True)
def main(N, XY):
query = to_integer_query(N, XY)
fact, fact_inv, inv = fact_table()
is_prime, primes = prime_table(N)

PF = np.ones(N + 1, np.int64)
for p in primes:
PF[p::p] = p

K = 30
P_CNT = np.zeros((N + 1, K), np.int64)
P_CNT[:, 0] = 1 << 60

lcm = 1

def get_power(p):
nonlocal P_CNT
for k in range(K - 1, -1, -1):
if P_CNT[p, k]:
return k
return 0

nonlocal lcm
while n > 1:
p = PF[n]
e = 0
while n % p == 0:
n //= p
e += 1
k = get_power(p)
lcm = lcm * inv[p**k] % MOD
P_CNT[p, e] += coef
k = get_power(p)
lcm = lcm * (p**k) % MOD

Q = len(query) // 3
for q in range(Q):
add(query[3 * q + 0, 0], query[3 * q + 0, 1])
add(query[3 * q + 1, 0], query[3 * q + 1, 1])
add(query[3 * q + 2, 0], query[3 * q + 2, 1])
print(lcm)

main(N, XY)```

#### Submission Info

Submission Time 2021-03-04 06:28:09+0900 K - Permutation Period maspy Python (3.8.2) 100 4838 Byte AC 1426 ms 148256 KB

#### Judge Result

Set Name All
Score / Max Score 100 / 100
Status
 AC × 27
Set Name Test Cases
All 00_sample_00, 00_sample_01, 00_sample_02, 10_small_rand_00, 10_small_rand_01, 10_small_rand_02, 10_small_rand_03, 15_small_rand_rev_00, 20_large_rand_00, 20_large_rand_01, 20_large_rand_02, 20_large_rand_03, 25_large_rand_rev_00, 30_rand_perm_00, 30_rand_perm_01, 30_rand_perm_02, 30_rand_perm_03, 40_long_period_00, 40_long_period_01, 40_long_period_02, 40_long_period_03, 40_long_period_04, 40_long_period_05, 50_long_one_period_00, 50_long_one_period_01, 50_long_one_period_02, 50_long_one_period_03
Case Name Status Exec Time Memory
00_sample_00 AC 551 ms 140264 KB
00_sample_01 AC 543 ms 139436 KB
00_sample_02 AC 589 ms 140444 KB
10_small_rand_00 AC 623 ms 146860 KB
10_small_rand_01 AC 622 ms 146936 KB
10_small_rand_02 AC 615 ms 146840 KB
10_small_rand_03 AC 621 ms 146772 KB
15_small_rand_rev_00 AC 620 ms 148012 KB
20_large_rand_00 AC 1380 ms 147304 KB
20_large_rand_01 AC 1426 ms 147676 KB
20_large_rand_02 AC 1359 ms 148256 KB
20_large_rand_03 AC 1138 ms 147700 KB
25_large_rand_rev_00 AC 738 ms 147448 KB
30_rand_perm_00 AC 726 ms 147384 KB
30_rand_perm_01 AC 724 ms 147744 KB
30_rand_perm_02 AC 723 ms 148236 KB
30_rand_perm_03 AC 721 ms 147648 KB
40_long_period_00 AC 867 ms 147748 KB
40_long_period_01 AC 876 ms 147792 KB
40_long_period_02 AC 899 ms 147396 KB
40_long_period_03 AC 961 ms 148236 KB
40_long_period_04 AC 1058 ms 148228 KB
40_long_period_05 AC 1036 ms 147384 KB
50_long_one_period_00 AC 1148 ms 147480 KB
50_long_one_period_01 AC 1185 ms 147724 KB
50_long_one_period_02 AC 1300 ms 147368 KB
50_long_one_period_03 AC 1121 ms 148116 KB