📑

# AtCoder ABC228 個人的メモ

2021/11/21に公開

## 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しそう。
なのでここを高速化したい。

これは区間最小値を求めることなのでセグ木を使えばおｋ

セグ木の実装部分
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とする。

しかしそのまま計算すると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をうまいこと計算するために公式解説のようにフェルマーの小定理を使って式変形すればおｋ。
この際にフェルマーの小定理はMPが互いに素(MPの最大公約数が1)である必要がある。
Pは素数なので約数が1Pしかないため、MPの最大公約数も1Pのみになる。
なのでMPの倍数でないならばMPの最大公約数は1となり、MPが互いに素と分かる。

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)