結果
| 問題 |
No.3002 多項式の割り算 〜easy〜
|
| ユーザー |
 hidehic0
|
| 提出日時 | 2025-01-17 21:32:16 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 12,008 bytes |
| コンパイル時間 | 2,396 ms |
| コンパイル使用メモリ | 81,664 KB |
| 実行使用メモリ | 86,528 KB |
| 最終ジャッジ日時 | 2025-01-17 21:32:39 |
| 合計ジャッジ時間 | 7,596 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 WA * 1 |
| other | WA * 22 |
ソースコード
r"""
______________________
< it's hidehico's code >
----------------------
\
\
.--.
|o_o |
|:_/ |
// \ \
(| | )
/'\_ _/`\
\___)=(___/
"""
# ライブラリと関数と便利変数
# ライブラリ
import bisect
import heapq
import sys
import unittest
from collections import Counter, defaultdict, deque
from itertools import permutations
from math import gcd, lcm, pi
from typing import Any, List
# from atcoder.segtree import SegTree
# from atcoder.lazysegtree import LazySegTree
# from atcoder.dsu import DSU
# cortedcontainersは使うときだけ wandbox非対応なので
# from sortedcontainers import SortedDict, SortedSet, SortedList
# import pypyjit
# pypyjit.set_param("max_unroll_recursion=-1")
sys.setrecursionlimit(5 * 10**5)
# 数学型関数
def is_prime(n):
if n == 1:
return False
def f(a, t, n):
x = pow(a, t, n)
nt = n - 1
while t != nt and x != 1 and x != nt:
x = pow(x, 2, n)
t <<= 1
return t & 1 or x == nt
if n == 2:
return True
elif n % 2 == 0:
return False
d = n - 1
d >>= 1
while d & 1 == 0:
d >>= 1
checklist = (
[2, 7, 61] if 2**32 > n else [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
)
for i in checklist:
if i >= n:
break
if not f(i, d, n):
return False
return True
def eratosthenes(n):
primes = [True] * (n + 1)
primes[0], primes[1] = False, False
i = 2
while i**2 <= n:
if primes[i]:
for k in range(i * 2, n + 1, i):
primes[k] = False
i += 1
return [i for i, p in enumerate(primes) if p]
def calc_divisors(N):
# 約数全列挙
import heapq
result = []
for i in range(1, N + 1):
if i * i > N:
break
if N % i != 0:
continue
heapq.heappush(result, i)
if N // i != i:
heapq.heappush(result, N // i)
return result
def factorization(n):
# 素因数分解
result = []
tmp = n
for i in range(2, int(-(-(n**0.5) // 1)) + 1):
if tmp % i == 0:
cnt = 0
while tmp % i == 0:
cnt += 1
tmp //= i
result.append([i, cnt])
if tmp != 1:
result.append([tmp, 1])
if result == []:
result.append([n, 1])
return result
def simple_sigma(n: int) -> int:
r"""
1からnまでの総和を求める関数
つまり和の公式
"""
return (n * (n + 1)) // 2
# 多次元配列作成
from typing import List, Any
def create_array2(a: int, b: int, default: Any = 0) -> List[List[Any]]:
"""
２次元配列を初期化する関数
"""
return [[default] * b for _ in [0] * a]
def create_array3(a: int, b: int, c: int, default: Any = 0) -> List[List[List[Any]]]:
"""
３次元配列を初期化する関数
"""
return [[[default] * c for _ in [0] * b] for _ in [0] * a]
from typing import Callable
def binary_search(fn: Callable[[int], bool], right: int = 0, left: int = -1) -> int:
"""
二分探索の抽象的なライブラリ
評価関数の結果に応じて、二分探索する
最終的にはleftを出力します
関数のテンプレート
def check(mid:int):
if A[mid] > x:
return True
else:
return False
midは必須です。それ以外はご自由にどうぞ
"""
while right - left > 1:
mid = (left + right) // 2
if fn(mid):
left = mid
else:
right = mid
return left
# 標準入力関数
import sys
# 一行に一つのstring
def s():
return sys.stdin.readline().rstrip()
# 一行に複数のstring
def sl():
return s().split()
# 一つのint
def ii():
return int(s())
# 一行に複数のint
def il(add_num: int = 0):
return list(map(lambda i: int(i) + add_num, sl()))
# 複数行の入力をサポート
def li(n: int, func, *args):
return [func(*args) for _ in [0] * n]
# YesNo関数
def YesNoTemplate(state: bool, upper: bool = False) -> str:
"""
stateがTrueなら、upperに応じてYes,YESをreturn
stateがFalseなら、upperに応じてNo,NOをreturnする
"""
YES = ["Yes", "YES"]
NO = ["No", "NO"]
if state:
return YES[int(upper)]
else:
return NO[int(upper)]
def YN(state: bool, upper: bool = False) -> None:
"""
先程のYesNoTemplate関数の結果を出力する
"""
res = YesNoTemplate(state, upper)
print(res)
def YE(state: bool, upper: bool = False) -> bool | None:
"""
boolがTrueならYesを出力してexit
"""
if not state:
return False
YN(True, upper)
exit()
def NE(state: bool, upper: bool = False) -> bool | None:
"""
boolがTrueならNoを出力してexit
"""
if not state:
return False
YN(False, upper)
exit()
def coordinate_check(x: int, y: int, H: int, W: int) -> bool:
"""
座標がグリッドの範囲内にあるかチェックする関数
0-indexedが前提
"""
return 0 <= x < H and 0 <= y < W
from typing import List, Tuple
def grid_moves(
x: int,
y: int,
H: int,
W: int,
moves: List[Tuple[int]] = [(0, 1), (0, -1), (1, 0), (-1, 0)],
*check_funcs,
) -> List[Tuple[int]]:
"""
現在の座標から、移動可能な座標をmovesをもとに列挙します。
xとyは現在の座標
HとWはグリッドのサイズ
movesは移動する座標がいくつかを保存する
check_funcsは、その座標の点が#だとかを自前で実装して判定はこちらでするみたいな感じ
なおcheck_funcsは引数がxとyだけというのが条件
"""
res = []
for mx, my in moves:
nx, ny = x + mx, y + my
if not coordinate_check(nx, ny, H, W):
continue
for f in check_funcs:
if not f(nx, ny):
break
else:
res.append((nx, ny))
return res
# ac_libraryのメモ
"""
segtree
初期化するとき
Segtree(op,e,v)
opはマージする関数
例
def op(a,b):
return a+b
eは初期化する値
vは配列の長さまたは、初期化する内容
"""
# グラフ構造
# 無向グラフ
from collections import deque
from typing import List
class Graph:
def __init__(self, N: int, dire: bool = False) -> None:
self.N = N
self.dire = dire
self.grath = [[] for _ in [0] * self.N]
self.in_deg = [0] * N
def new_side(self, a: int, b: int):
# 注意 0-indexedが前提
self.grath[a].append(b)
if self.dire:
self.in_deg[b] += 1
if not self.dire:
self.grath[b].append(a)
def side_input(self):
# 新しい辺をinput
a, b = map(lambda x: int(x) - 1, input().split())
self.new_side(a, b)
def input(self, M: int):
# 複数行の辺のinput
for _ in [0] * M:
self.side_input()
def get(self, a: int):
# 頂点aの隣接点を出力
return self.grath[a]
def all(self):
# グラフの内容をすべて出力
return self.grath
def topological(self, unique: bool = False):
if not self.dire:
raise ValueError("グラフが有向グラフでは有りません (╥﹏╥)")
in_deg = self.in_deg[:]
S: deque[int] = deque([])
order: List[int] = []
for i in range(self.N):
if in_deg[i] == 0:
S.append(i)
while S:
if unique and len(S) != 1:
return [-1]
cur = S.pop()
order.append(cur)
for nxt in self.get(cur):
in_deg[nxt] -= 1
if in_deg[nxt] == 0:
S.append(nxt)
if sum(in_deg) > 0:
return [-1]
else:
return [x for x in order]
# 重み付きグラフ
class GraphW:
def __init__(self, N: int, dire: bool = False) -> None:
self.N = N
self.dire = dire
self.grath = [[] for _ in [0] * self.N]
def new_side(self, a: int, b: int, w: int):
# 注意 0-indexedが前提
self.grath[a].append((b, w))
if not self.dire:
self.grath[b].append((a, w))
def side_input(self):
# 新しい辺をinput
a, b, w = map(lambda x: int(x) - 1, input().split())
self.new_side(a, b, w + 1)
def input(self, M: int):
# 複数行の辺のinput
for _ in [0] * M:
self.side_input()
def get(self, a: int):
# 頂点aの隣接点を出力
return self.grath[a]
def all(self):
# グラフの内容をすべて出力
return self.grath
# UnionFind木
class UnionFind:
"""
rollbackをデフォルトで装備済み
計算量は、経路圧縮を行わないため、基本的なUnionFindの動作は、一回あたり、O(log N)
rollbackは、一回あたり、O(1)で行える。
"""
def __init__(self, n: int) -> None:
self.size = n
self.data = [-1] * n
self.hist = []
def root(self, vtx: int) -> int:
if self.data[vtx] < 0:
return vtx
return self.root(self.data[vtx])
def same(self, a: int, b: int):
return self.root(a) == self.root(b)
def unite(self, a: int, b: int) -> bool:
"""
rootが同じでも、履歴には追加する
"""
ra, rb = self.root(a), self.root(b)
# 履歴を作成する
new_hist = [ra, rb, self.data[ra], self.data[rb]]
self.hist.append(new_hist)
if ra == rb:
return False
if self.data[ra] > self.data[rb]:
ra, rb = rb, ra
self.data[ra] += self.data[rb]
self.data[rb] = ra
return True
def rollback(self):
if not self.hist:
return False
ra, rb, da, db = self.hist.pop()
self.data[ra] = da
self.data[rb] = db
return True
# Trie木
class Trie:
class Data:
def __init__(self, value, ind):
self.count = 1
self.value = value
self.childs = {}
self.ind = ind
def __init__(self):
self.data = [self.Data("ab", 0)] # 初期値はabにして被らないようにする
def add(self, value: str) -> int:
cur = 0
result = 0
# 再帰的に探索する
for t in value:
childs = self.data[cur].childs # 参照渡しで
if t in childs:
self.data[childs[t]].count += 1
else:
nd = self.Data(t, len(self.data))
childs[t] = len(self.data)
self.data.append(nd)
result += self.data[childs[t]].count - 1
cur = childs[t]
return result
def lcp_max(self, value: str) -> int:
cur = 0
result = 0
for t in value:
childs = self.data[cur].childs
if t not in childs:
break
if self.data[childs[t]].count == 1:
break
cur = childs[t]
result += 1
return result
def lcp_sum(self, value: str) -> int:
cur = 0
result = 0
for t in value:
childs = self.data[cur].childs
if t not in childs:
break
if self.data[childs[t]].count == 1:
break
cur = childs[t]
result += self.data[childs[t]].count - 1
return result
# 便利変数
INF = 1 << 63
lowerlist = list("abcdefghijklmnopqrstuvwxyz")
upperlist = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# コード
A, B = il()
print(0, pow(A, B, 3))