結果
| 問題 | No.3533 Difficult Counting Problem? |
| コンテスト | |
| ユーザー |
 もの
|
| 提出日時 | 2026-05-08 21:37:36 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 127 ms / 2,000 ms |
| コード長 | 18,179 bytes |
| 記録 | |
| コンパイル時間 | 349 ms |
| コンパイル使用メモリ | 85,120 KB |
| 実行使用メモリ | 97,152 KB |
| 最終ジャッジ日時 | 2026-05-08 21:37:48 |
| 合計ジャッジ時間 | 4,704 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 17 |
ソースコード
############################################################################################
import bisect,collections,copy,heapq,itertools,math,string,sys,queue,time,random
from decimal import Decimal
from typing import List, Optional, Tuple
import sys
def I() -> str:
"""
標準入力から1行読み取る（改行なし）
Returns:
入力された文字列
"""
return input()
def IS():
"""
標準入力から1行読み取り、空白で分割する
Returns:
分割された文字列のリスト
"""
return input().split()
def II() -> int:
"""
標準入力から整数を1つ読み取る
Returns:
入力された整数
"""
return int(input())
def IIS():
"""
標準入力から1行読み取り、空白で分割して整数のリストにする
Returns:
整数のリスト
使い方:
a, b = IIS() # 2つの整数を受け取る
arr = IIS() # 任意個の整数をリストで受け取る
"""
return list(map(int, input().split()))
def LIIS():
"""
IIS() のエイリアス
標準入力から1行読み取り、空白で分割して整数のリストにする
Returns:
整数のリスト
"""
return list(map(int, input().split()))
"""
べき乗の高速計算・逆元の計算
機能:
- 繰り返し二乗法による高速なべき乗計算 O(log N)
- 逆元の計算（フェルマーの小定理） O(log mod)
- 逆元の計算（拡張ユークリッドの互除法） O(log min(a, mod))
- 組み合わせ計算（mod込み）
使い方:
# べき乗
pow_mod(2, 10, 1000000007) # 2^10 mod 10^9+7
# 逆元
inv = mod_inverse(3, 1000000007) # 3の逆元 mod 10^9+7
# 組み合わせ
comb = Combination(10**6, 10**9+7)
print(comb.nCr(10, 3)) # 10C3
"""
from typing import Tuple
def pow_mod(a: int, n: int, mod: int) -> int:
"""a^n mod mod を高速に計算する（繰り返し二乗法）
Args:
a: 底
n: 指数
mod: 法
Returns:
a^n mod mod
計算量: O(log N)
"""
result = 1
a %= mod
while n > 0:
if n & 1:
result = (result * a) % mod
a = (a * a) % mod
n >>= 1
return result
def mod_inverse_fermat(a: int, mod: int) -> int:
"""フェルマーの小定理による逆元の計算
mod が素数の場合に使用可能
a^(-1) ≡ a^(mod-2) (mod mod)
Args:
a: 逆元を求める数
mod: 法（素数）
Returns:
a の逆元 mod mod
計算量: O(log mod)
"""
return pow_mod(a, mod - 2, mod)
def extgcd(a: int, b: int) -> Tuple[int, int, int]:
"""拡張ユークリッドの互除法
ax + by = gcd(a, b) を満たす x, y を求める
Args:
a, b: 整数
Returns:
(gcd(a, b), x, y)
計算量: O(log min(a, b))
"""
if b == 0:
return a, 1, 0
g, x, y = extgcd(b, a % b)
return g, y, x - (a // b) * y
def mod_inverse_extgcd(a: int, mod: int) -> int:
"""拡張ユークリッドの互除法による逆元の計算
mod が素数でなくても使用可能（gcd(a, mod) = 1 が必要）
Args:
a: 逆元を求める数
mod: 法
Returns:
a の逆元 mod mod（存在しない場合は -1）
計算量: O(log min(a, mod))
"""
g, x, _ = extgcd(a, mod)
if g != 1:
return -1 # 逆元が存在しない
return x % mod
class Combination:
"""組み合わせ計算（mod 込み）
階乗と逆元を前計算して高速に nCr を計算する
"""
def __init__(self, n: int, mod: int):
"""
Args:
n: 計算する組み合わせの最大値
mod: 法（素数）
計算量: O(N)
"""
self.n = n
self.mod = mod
# 階乗を前計算
self.fact = [1] * (n + 1)
for i in range(1, n + 1):
self.fact[i] = (self.fact[i - 1] * i) % mod
# 逆元を前計算
self.inv_fact = [1] * (n + 1)
self.inv_fact[n] = mod_inverse_fermat(self.fact[n], mod)
for i in range(n - 1, -1, -1):
self.inv_fact[i] = (self.inv_fact[i + 1] * (i + 1)) % mod
def nCr(self, n: int, r: int) -> int:
"""nCr mod mod を計算する
Args:
n, r: 組み合わせのパラメータ
Returns:
nCr mod mod
計算量: O(1)
"""
if n < 0 or r < 0 or n < r:
return 0
return (self.fact[n] * self.inv_fact[r] % self.mod *
self.inv_fact[n - r] % self.mod)
def nPr(self, n: int, r: int) -> int:
"""nPr mod mod を計算する（順列）
Args:
n, r: 順列のパラメータ
Returns:
nPr mod mod
計算量: O(1)
"""
if n < 0 or r < 0 or n < r:
return 0
return (self.fact[n] * self.inv_fact[n - r] % self.mod)
def nHr(self, n: int, r: int) -> int:
"""重複組み合わせ nHr = (n+r-1)Cr
Args:
n, r: パラメータ
Returns:
nHr mod mod
計算量: O(1)
"""
return self.nCr(n + r - 1, r)
# def make_divisors(n: int) -> list[int]:
# """整数 n の約数をすべて列挙する
# Args:
# n: 約数を列挙する整数（n >= 1）
# Returns:
# n の約数のリスト（昇順）
# 計算量: O(√N)
# """
# lower_divisors = []
# upper_divisors = []
# i = 1
# while i * i <= n:
# if n % i == 0:
# lower_divisors.append(i)
# if i != n // i:
# upper_divisors.append(n // i)
# i += 1
# return lower_divisors + upper_divisors[::-1]
# sys.setrecursionlimit(10**7)
alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def bit_count(x):
return bin(x).count("1")
def yesno(f):
if f:print("Yes")
else:print("No")
MOD=998244353
from functools import lru_cache
INF=10**18
# import pypyjit
# pypyjit.set_param("trace_limit=24000,vec=1")
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import deque
from typing import List, Tuple
import heapq
class MaxFlow:
"""最大流アルゴリズム（Dinic法）"""
def __init__(self, n: int):
"""
Args:
n: 頂点数
"""
self.n = n
self.graph = [[] for _ in range(n)]
def add_edge(self, u: int, v: int, cap: int):
"""辺を追加する（u → v に容量capの辺）"""
self.graph[u].append([v, cap, len(self.graph[v])])
self.graph[v].append([u, 0, len(self.graph[u]) - 1])
def bfs(self, s: int, t: int) -> bool:
"""BFSでレベルグラフを構築する"""
self.level = [-1] * self.n
self.level[s] = 0
queue = deque([s])
while queue:
v = queue.popleft()
for to, cap, _ in self.graph[v]:
if cap > 0 and self.level[to] < 0:
self.level[to] = self.level[v] + 1
queue.append(to)
return self.level[t] >= 0
def dfs(self, v: int, t: int, f: int) -> int:
"""DFSで増加パスを見つけて流す"""
if v == t:
return f
for i in range(self.iter[v], len(self.graph[v])):
self.iter[v] = i
to, cap, rev = self.graph[v][i]
if cap > 0 and self.level[v] < self.level[to]:
d = self.dfs(to, t, min(f, cap))
if d > 0:
self.graph[v][i][1] -= d
self.graph[to][rev][1] += d
return d
return 0
def max_flow(self, s: int, t: int) -> int:
"""最大流を求める
Args:
s: 始点
t: 終点
Returns:
最大流量
"""
flow = 0
while self.bfs(s, t):
self.iter = [0] * self.n
while True:
f = self.dfs(s, t, float('inf'))
if f == 0:
break
flow += f
return flow
def min_cut(self, s: int) -> List[int]:
"""最小カットに含まれる頂点のリストを返す（始点側）
max_flow実行後に呼び出す。
"""
visited = [False] * self.n
queue = deque([s])
visited[s] = True
while queue:
v = queue.popleft()
for to, cap, _ in self.graph[v]:
if cap > 0 and not visited[to]:
visited[to] = True
queue.append(to)
return [i for i in range(self.n) if visited[i]]
class MinCostFlow:
"""最小費用流アルゴリズム（ダイクストラ法 + ポテンシャル）"""
def __init__(self, n: int):
"""
Args:
n: 頂点数
"""
self.n = n
self.graph = [[] for _ in range(n)]
def add_edge(self, u: int, v: int, cap: int, cost: int):
"""辺を追加する（u → v に容量cap、コストcostの辺）"""
self.graph[u].append([v, cap, cost, len(self.graph[v])])
self.graph[v].append([u, 0, -cost, len(self.graph[u]) - 1])
def min_cost_flow(self, s: int, t: int, max_flow: int) -> Tuple[int, int]:
"""最小費用流を求める
Args:
s: 始点
t: 終点
max_flow: 流す流量の上限
Returns:
(流量, 最小費用) のタプル
"""
res = 0
flow = 0
h = [0] * self.n
while flow < max_flow:
# ダイクストラ法で最短路を探す
dist = [float('inf')] * self.n
dist[s] = 0
prev_v = [-1] * self.n
prev_e = [-1] * self.n
pq = [(0, s)]
while pq:
d, v = heapq.heappop(pq)
if dist[v] < d:
continue
for i, (to, cap, cost, _) in enumerate(self.graph[v]):
if cap > 0 and dist[to] > dist[v] + cost + h[v] - h[to]:
dist[to] = dist[v] + cost + h[v] - h[to]
prev_v[to] = v
prev_e[to] = i
heapq.heappush(pq, (dist[to], to))
if dist[t] == float('inf'):
break
# ポテンシャルを更新
for v in range(self.n):
if dist[v] < float('inf'):
h[v] += dist[v]
# 流せる量を計算
d = max_flow - flow
v = t
while v != s:
d = min(d, self.graph[prev_v[v]][prev_e[v]][1])
v = prev_v[v]
# 流す
flow += d
res += d * h[t]
v = t
while v != s:
e = prev_e[v]
self.graph[prev_v[v]][e][1] -= d
rev = self.graph[prev_v[v]][e][3]
self.graph[v][rev][1] += d
v = prev_v[v]
return flow, res
class BipartiteMatching:
"""二部グラフの最大マッチング（Hopcroft-Karp: O(E√V)）"""
INF = float('inf')
def __init__(self, n: int, m: int):
self.n = n
self.m = m
self.graph = [[] for _ in range(n)]
self.match_right = [-1] * m
self.match_left = [-1] * n
self.dist_left = [0] * n # 左頂点の BFS 距離
def add_edge(self, u: int, v: int):
self.graph[u].append(v)
def _bfs(self) -> bool:
"""フェーズ開始時に最短増加パスの距離層を構築"""
queue = deque()
for v in range(self.n):
if self.match_left[v] == -1:
self.dist_left[v] = 0
queue.append(v)
else:
self.dist_left[v] = self.INF
found = False
while queue:
v = queue.popleft()
for to in self.graph[v]:
nxt = self.match_right[to]
if nxt == -1:
found = True
elif self.dist_left[nxt] == self.INF:
self.dist_left[nxt] = self.dist_left[v] + 1
queue.append(nxt)
return found
def _dfs(self, v: int) -> bool:
"""距離層に沿って増加パスを探す（使用済み辺を削除して再探索を防ぐ）"""
for to in self.graph[v]:
nxt = self.match_right[to]
if nxt == -1 or (
self.dist_left[nxt] == self.dist_left[v] + 1
and self._dfs(nxt)
):
self.match_right[to] = v
self.match_left[v] = to
return True
# この頂点からはもう増加パスなし → 距離を無効化して再訪を防ぐ
self.dist_left[v] = self.INF
return False
def max_matching(self) -> int:
res = 0
while self._bfs(): # √V 回程度で終了
for v in range(self.n):
if self.match_left[v] == -1 and self._dfs(v):
res += 1
return res
def get_matching(self) -> List[Tuple[int, int]]:
return [
(self.match_right[v], v)
for v in range(self.m)
if self.match_right[v] != -1
]
class MinVertexCover:
"""二部グラフの最小点被覆（ケーニッヒの定理）"""
def __init__(self, n: int, m: int):
"""
Args:
n: 左側の頂点数
m: 右側の頂点数
"""
self.n = n
self.m = m
self.matching = BipartiteMatching(n, m)
def add_edge(self, u: int, v: int):
"""辺を追加する（左側のu → 右側のv）"""
self.matching.add_edge(u, v)
def min_vertex_cover(self) -> Tuple[int, List[int], List[int]]:
"""最小点被覆を求める
Returns:
(最小点被覆数, 左側の頂点リスト, 右側の頂点リスト)
"""
max_match = self.matching.max_matching()
visited_left = [False] * self.n
visited_right = [False] * self.m
# マッチングされていない左側の頂点からDFS
def dfs(v: int):
if visited_left[v]:
return
visited_left[v] = True
for to in self.matching.graph[v]:
if not visited_right[to]:
visited_right[to] = True
if self.matching.match_right[to] != -1:
dfs(self.matching.match_right[to])
for v in range(self.n):
if self.matching.match_left[v] == -1:
dfs(v)
# 最小点被覆: 訪問されなかった左側 + 訪問された右側
left_cover = [v for v in range(self.n) if not visited_left[v]]
right_cover = [v for v in range(self.m) if visited_right[v]]
return max_match, left_cover, right_cover
class MaxIndependentSet:
"""二部グラフの最大独立集合"""
def __init__(self, n: int, m: int):
"""
Args:
n: 左側の頂点数
m: 右側の頂点数
"""
self.n = n
self.m = m
self.min_cover = MinVertexCover(n, m)
def add_edge(self, u: int, v: int):
"""辺を追加する（左側のu → 右側のv）"""
self.min_cover.add_edge(u, v)
def max_independent_set(self) -> Tuple[int, List[int], List[int]]:
"""最大独立集合を求める
Returns:
(最大独立集合数, 左側の頂点リスト, 右側の頂点リスト)
"""
cover_size, left_cover, right_cover = self.min_cover.min_vertex_cover()
left_cover_set = set(left_cover)
right_cover_set = set(right_cover)
left_independent = [v for v in range(self.n) if v not in left_cover_set]
right_independent = [v for v in range(self.m) if v not in right_cover_set]
independent_size = self.n + self.m - cover_size
return independent_size, left_independent, right_independent
class MinEdgeCover:
"""二部グラフの最小辺被覆"""
def __init__(self, n: int, m: int):
"""
Args:
n: 左側の頂点数
m: 右側の頂点数
"""
self.n = n
self.m = m
self.matching = BipartiteMatching(n, m)
self.graph = [[] for _ in range(n)]
def add_edge(self, u: int, v: int):
"""辺を追加する（左側のu → 右側のv）"""
self.matching.add_edge(u, v)
self.graph[u].append(v)
def min_edge_cover(self) -> Tuple[int, List[Tuple[int, int]]]:
"""最小辺被覆を求める
Returns:
(最小辺被覆数, 辺のリスト)
"""
max_match = self.matching.max_matching()
matching_edges = self.matching.get_matching()
matched_left = set()
matched_right = set()
for u, v in matching_edges:
matched_left.add(u)
matched_right.add(v)
edges = list(matching_edges)
# 左側の未マッチ頂点に辺を追加
for u in range(self.n):
if u not in matched_left and self.graph[u]:
edges.append((u, self.graph[u][0]))
# 右側の未マッチ頂点に辺を追加
for u in range(self.n):
for v in self.graph[u]:
if v not in matched_right:
edges.append((u, v))
matched_right.add(v)
break
return len(edges), edges
####################################################
t=II()
for _ in range(t):
n=II()
if n==1:
print(1)
else:
print(0)