from itertools import combinations
def C():
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
ans = 0
for com in combinations(range(H + W - 2), r=H - 1):
route = [True] * (H + W - 2)
for c in com: route[c] = False
h = 0
w = 0
numbers = set([A[h][w]])
for nxt in route:
if nxt: w += 1
else: h += 1
numbers.add(A[h][w])
if len(numbers) == H + W - 1: ans += 1
# print(numbers)
print(ans)
test_all(C)
def C():
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
nums = [None] * (H + W - 1)
ans = 0
st = [(0, 0)]
while st:
h, w = st.pop()
if A[h][w] in nums[:h + w]: continue
nums[h + w] = A[h][w]
if h + w == H + W - 2:
ans += 1
else:
if h < H - 1: st.append((h + 1, w))
if w < W - 1: st.append((h, w + 1))
print(ans)
test_all(C)
test_dataD = [
{
"in":"""5 3
3 R 5 B
5 R 3 B
4 R 2 B
""",
"out": """1 2
"""
},{
"in":"""7 0
""",
"out": """0 7
"""
},{
"in":"""7 6
5 R 3 R
7 R 4 R
4 B 1 R
2 R 3 B
2 B 5 B
1 B 7 B
""",
"out": """2 1
"""
},
]def D():
pass
test_all(D)
自由欄
コンテスト中
連結成分、サイクル、と言えばもはやおなじみDSUですね。
from collections import defaultdict
class DSU():
def __init__(self, n=None):
self.dsu = defaultdict(lambda: -1)
if n:
for i in range(n): self.dsu[i]
def leader(self, i):
if self.dsu[i] < 0: return i
self.dsu[i] = self.leader(self.dsu[i])
return self.dsu[i]
def merge(self, i, j):
'''サイズの大きい方(x)に小さい方(y)をマージ'''
if i == j: return
x = self.leader(i)
y = self.leader(j)
if x == y: return
if self.dsu[x] > self.dsu[y]: x, y = y, x
self.dsu[x] += self.dsu[y]
self.dsu[y] = x
def members(self, i):
l = self.leader(i)
return [k for k, v in self.dsu.items() if self.leader(k) == l]
def __len__(self):
return len([1 for v in self.dsu.values() if v < 0])def D():
N, M = map(int, input().split())
dsu = DSU(N + 1)
circle = 0
for _ in range(M):
a, _, b, _ = input().split()
a = int(a)
b = int(b)
if dsu.leader(a) == dsu.leader(b):
circle += 1
else:
dsu.merge(a, b)
leaders = set()
for i in range(1, N + 1):
leaders.add(dsu.leader(i))
print(circle, len(leaders) - circle)
test_all(D)
以下、自分なりに咀嚼してコーディングしてみましたが、結局解説 by shakayamiの実装例通りになってしまいました。
せめてオリジナリティを出そうとpow関数的なヤツを自作してみましたが、特に意味はありません😇
from functools import lru_cache
@lru_cache(None)
def exp(base, e, M):
if e == 1: return base
ret = base if e & 1 else 1
e >>= 1
cnt = 2
while e:
if e & 1: ret = ret * exp(base, cnt // 2, M) ** 2 % M
e >>= 1
cnt *= 2
return ret % M
def f1(a, x, M):
if x == 1: return 1 % M
elif x % 2: return (f1(a, x - 1, M) + exp(a, x - 1, M)) % M
else: return ((1 + exp(a, x // 2, M)) * f1(a, x // 2, M)) % M
def f2(a, x, M):
if x == 1: return 1 % M
elif x % 2: return (1 + a * f2(a, x - 1, M)) % M
else: return (1 + a) * f2(a * a % M, x // 2, M) % M
(1)の場合
def E():
A, X, M = map(int, input().split())
print(f1(A, X, M))
test_all(E)
AtCoder Inc.
