AtCoder ABC228 個人的メモ

A - On and Off

S, T, X = map(int, input().split())

if S <= X < T:
    print("Yes")
elif S > T and (X < T or S <= X):
    print("Yes")
else:
    print("No")

B - Takahashi's Secret

N, X = map(int, input().split())
A = list(map(int, input().split()))  # 整数を入力

seen = [0] * (N + 1)
ans = 0
now = X
while seen[now] == 0:
    seen[now] = 1
    now = A[now - 1]
    ans += 1

print(ans)

C - Final Day

from itertools import accumulate

N, K = map(int, input().split())
P = [list(map(int, input().split())) for _ in range(N)]  # 整数を入力

P = [sum(p) for p in P]
# 3日目までの総得点がi点の人数
num_score = [0] * (1200 + 2)
for p in P:
    num_score[p] += 1
# 3日目までの得点がi点以上の人数
cumsum = list(accumulate(num_score[::-1]))[::-1]

for p in P:
    num_highers = min(len(num_score), p + 301)
    if cumsum[num_highers] + 1 <= K:
        print("Yes")
    else:
        print("No")

D - Linear Probing

この問題でネックになるのは$t_i=1$の時の処理2
この処理を愚直に実装すると、最悪の場合に$i$個目のクエリで$i$の計算量が掛かるのでtleしそう。
なのでここを高速化したい。
処理2は$h\ mod\ N$以降の範囲で未更新のインデックスがどこかを$O(10)$ぐらいで求めることができればおｋ
言い換えると、$h\ mod\ N$以上で最小の値 又は $h\ mod\ N$以下で最小の値 を$O(10)$ぐらいで求めたい
これは区間最小値を求めることなのでセグ木を使えばおｋ

セグ木の実装部分

class segtree:
    """
    Segment tree\\
    Store value as object type and optional function for binary operarion.\\
    "get" function return a value by binary operarion result. O(logN)\\
    "update" function update tree's a value. O(logN)

    Attributes
    ----------
    n : int
        Number of elements
    identity element_func : func
        Identity_element for initialization.\\
        If operator is * and identiry element is e, e * A = A and A * e = A.
    binary_operation_func : func
        Function for binary operation x and y.\\
        Function must have associative law.\\
        If operator is *, (A * B) * C = A * (B * C).

    Methods
    -------
    update(i, x)
        Update tree[i] value to x
    get(a, b)
        Get value from [a, b).\\
        Include a but not include b, return a merged value.
    """

    def __init__(self, n: int, identity_element_func, binary_operation_func):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of elements
        identity_element_func : func
            Identity element for initialization\\
            If operator is * and identiry element is e, e * A = A and A * e = A
        binary_operation_func : func
            Function for binary operation x and y.\\
            Function must have associative law.\\
            If operator is *, (A * B) * C = A * (B * C)
        """
        self.identity = identity_element_func
        self.binary = binary_operation_func
        self.offset = 1 << (n - 1).bit_length()  # offsetはnより大きい2の冪数
        self.tree = [self.identity() for _ in range(self.offset << 1)]

    @classmethod
    def from_array(cls, arr, identity_element_func, binary_operation_func):
        """Initialize from array"""
        ins = cls(len(arr), identity_element_func, binary_operation_func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            lch = i << 1
            ins.tree[i] = binary_operation_func(
                ins.tree[lch], ins.tree[lch + 1])
        return ins

    def update(self, index: int, x: int):
        """
        Overwrite segment-tree's a value and update parent nodes.
        This method updates the value to the new value regardless of the previous value.

        Parameters
        ----------
        index : int
            index of update value
        x : int
            new value
        """
        index += self.offset
        self.tree[index] = x
        while index > 1:
            index >>= 1  # 右ビットシフトで親ノードのインデックスへ移動
            lch = index << 1
            self.tree[index] = self.binary(self.tree[lch], self.tree[lch + 1])

    def get(self, left: int, right: int) -> int:
        """
        Get a specific value by result of binary operation from interval [left, right).

        Parameters
        ----------
        left, right : int
            Index of interval.\\
            This is hald open interval, this interval include left but not right.
        """
        result_l = self.identity()
        result_r = self.identity()
        left += self.offset
        right += self.offset
        while left < right:
            if left & 1:
                result_l = self.binary(result_l, self.tree[left])
                left += 1
            if right & 1:
                right -= 1
                result_r = self.binary(self.tree[right], result_r)
            left >>= 1
            right >>= 1

        return self.binary(result_l, result_r)

N = pow(2, 20)
Q = int(input())
INF = 10 ** 19
minimum_lst = segtree.from_array(range(N), lambda: INF, min)
ans = [-1] * N

for _ in range(Q):
    t, x = map(int, input().split())

    i = x % N
    if t == 1:
        h_mod_n = minimum_lst.get(i, N)
        if h_mod_n == INF:
            h_mod_n = minimum_lst.get(0, i)

        minimum_lst.update(h_mod_n, INF)
        ans[h_mod_n] = x

    else:
        print(ans[i])

E - Integer Sequence Fair

$P=998244353$とする。
整数列が$K^N$通りでそれらに$M$通りの点数をつけることができるから、答えは$M^{K^N}(mod\ P)$となる。
しかしそのまま計算すると$M,K,N\leq 10^{18}$なのでtleする。($a=K^N(mod\ P)$として$M^a(mod\ P)$を求めるのは間違い。$(N,K,M,P)=(3,3,3,5)$とかが反例)
なので、$K^N$をうまいこと計算するために公式解説のようにフェルマーの小定理を使って式変形すればおｋ。
この際にフェルマーの小定理は$M$と$P$が互いに素($M$と$P$の最大公約数が$1$)である必要がある。
$P$は素数なので約数が$1$と$P$しかないため、$M$と$P$の最大公約数も$1$か$P$のみになる。
なので$M$が$P$の倍数でないならば$M$と$P$の最大公約数は$1$となり、$M$と$P$が互いに素と分かる。

from math import gcd

N, K, M = map(int, input().split())
P = 998244353

if gcd(M, P) == 1:
    sequence_pat = pow(K, N, P - 1)
    score_pat = pow(M, sequence_pat, P)
    print(score_pat)

else:
    print(0)