Submission #20639012


Source Code Expand

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

BACKET = 256
MOD = 1_000_000_007

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

@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:行き先が変更される可能性のあるインデックス
        (head, tail, node_size, root, cycle_size)
        """
        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
            head = v
            while P[v] != a:
                data[a, 4] += 1
                if change[v] or change[P[v]]:
                    v = P[v]
                    head = v
                    data[v] = (v, v, 1, a, -1)
                else:
                    v = P[v]
                    data[head, 1] = v
                    data[head, 2] += 1
                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

    def add(coef, n):
        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)

N, Q = from_readline()
XY = from_read().reshape(Q, 2)

main(N, XY)

Submission Info

Submission Time
Task K - Permutation Period
User maspy
Language Python (3.8.2)
Score 100
Code Size 4838 Byte
Status AC
Exec Time 1426 ms
Memory 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