結果
問題 | No.2326 Factorial to the Power of Factorial to the... |
ユーザー | McGregorsh |
提出日時 | 2023-05-29 23:12:59 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 12,597 bytes |
コンパイル時間 | 368 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 93,440 KB |
最終ジャッジ日時 | 2024-12-28 10:46:23 |
合計ジャッジ時間 | 7,129 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | WA | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | WA | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | WA | - |
testcase_14 | RE | - |
testcase_15 | WA | - |
testcase_16 | RE | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | RE | - |
testcase_20 | AC | 176 ms
91,136 KB |
testcase_21 | AC | 180 ms
91,136 KB |
ソースコード
###順序付き多重集合###import mathfrom bisect import bisect_left, bisect_right, insortfrom typing import Generic, Iterable, Iterator, TypeVar, Union, ListT = TypeVar('T')class SortedMultiset(Generic[T]):BUCKET_RATIO = 50REBUILD_RATIO = 170def _build(self, a=None) -> None:"Evenly divide `a` into buckets."if a is None: a = list(self)size = self.size = len(a)bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))self.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]def __init__(self, a: Iterable[T] = []) -> None:"Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"a = list(a)if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):a = sorted(a)self._build(a)def __iter__(self) -> Iterator[T]:for i in self.a:for j in i: yield jdef __reversed__(self) -> Iterator[T]:for i in reversed(self.a):for j in reversed(i): yield jdef __len__(self) -> int:return self.sizedef __repr__(self) -> str:return "SortedMultiset" + str(self.a)def __str__(self) -> str:s = str(list(self))return "{" + s[1 : len(s) - 1] + "}"def _find_bucket(self, x: T) -> List[T]:"Find the bucket which should contain x. self must not be empty."for a in self.a:if x <= a[-1]: return areturn adef __contains__(self, x: T) -> bool:if self.size == 0: return Falsea = self._find_bucket(x)i = bisect_left(a, x)return i != len(a) and a[i] == xdef count(self, x: T) -> int:"Count the number of x."return self.index_right(x) - self.index(x)def add(self, x: T) -> None:"Add an element. / O(√N)"if self.size == 0:self.a = [[x]]self.size = 1returna = self._find_bucket(x)insort(a, x)self.size += 1if len(a) > len(self.a) * self.REBUILD_RATIO:self._build()def discard(self, x: T) -> bool:"Remove an element and return True if removed. / O(√N)"if self.size == 0: return Falsea = self._find_bucket(x)i = bisect_left(a, x)if i == len(a) or a[i] != x: return Falsea.pop(i)self.size -= 1if len(a) == 0: self._build()return Truedef lt(self, x: T) -> Union[T, None]:"Find the largest element < x, or None if it doesn't exist."for a in reversed(self.a):if a[0] < x:return a[bisect_left(a, x) - 1]def le(self, x: T) -> Union[T, None]:"Find the largest element <= x, or None if it doesn't exist."for a in reversed(self.a):if a[0] <= x:return a[bisect_right(a, x) - 1]def gt(self, x: T) -> Union[T, None]:"Find the smallest element > x, or None if it doesn't exist."for a in self.a:if a[-1] > x:return a[bisect_right(a, x)]def ge(self, x: T) -> Union[T, None]:"Find the smallest element >= x, or None if it doesn't exist."for a in self.a:if a[-1] >= x:return a[bisect_left(a, x)]def __getitem__(self, x: int) -> T:"Return the x-th element, or IndexError if it doesn't exist."if x < 0: x += self.sizeif x < 0: raise IndexErrorfor a in self.a:if x < len(a): return a[x]x -= len(a)raise IndexErrordef index(self, x: T) -> int:"Count the number of elements < x."ans = 0for a in self.a:if a[-1] >= x:return ans + bisect_left(a, x)ans += len(a)return ansdef index_right(self, x: T) -> int:"Count the number of elements <= x."ans = 0for a in self.a:if a[-1] > x:return ans + bisect_right(a, x)ans += len(a)return ans###セグメントツリー########segfunc#####def segfunc(x, y):return max(x, y)# 最小値 min(x, y)# 最大値 max(x, y)# 区間和 x + y# 区間積 x * y# 最大公約数 math.gcd(x, y)# 排他的論理和 x ^ y######################ide_ele#####ide_ele = 0# 最小値 float('inf')# 最大値 -float('inf')# 区間和 0# 区間積 1# 最大公約数 0# 排他的論理和 0#################class SegTree:"""init(init_val, ide_ele): 配列init_valで初期化 O(N)update(k, x): k番目の値をxに更新 O(logN)query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)"""def __init__(self, init_val, segfunc, ide_ele):"""init_val: 配列の初期値segfunc: 区間にしたい操作ide_ele: 単位元n: 要素数num: n以上の最小の2のべき乗tree: セグメント木(1-index)"""n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1 << (n - 1).bit_length()self.tree = [ide_ele] * 2 * self.num# 配列の値を葉にセットfor i in range(n):self.tree[self.num + i] = init_val[i]# 構築していくfor i in range(self.num - 1, 0, -1):self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])def update(self, k, x):"""k番目の値をxに更新k: index(0-index)x: update value"""k += self.numself.tree[k] = xwhile k > 1:self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])k >>= 1def query(self, l, r):"""[l, r)のsegfuncしたものを得るl: index(0-index)r: index(0-index)"""res = self.ide_elel += self.numr += self.numwhile l < r:if l & 1:res = self.segfunc(res, self.tree[l])l += 1if r & 1:res = self.segfunc(res, self.tree[r - 1])l >>= 1r >>= 1return res###UnionFind###class UnionFind:"""0-indexed"""def __init__(self, n):self.n = nself.parent = [-1] * nself.__group_count = n # 辺がないとき、連結成分はn個ありますdef unite(self, x, y):"""xとyをマージ"""x = self.root(x)y = self.root(y)if x == y:return 0self.__group_count -= 1 # 木と木が合体するので、連結成分数が1減りますif self.parent[x] > self.parent[y]:x, y = y, xself.parent[x] += self.parent[y]self.parent[y] = xreturn self.parent[x]def is_same(self, x, y):"""xとyが同じ連結成分か判定"""return self.root(x) == self.root(y)def root(self, x):"""xの根を取得"""if self.parent[x] < 0:return xelse:self.parent[x] = self.root(self.parent[x])return self.parent[x]def size(self, x):"""xが属する連結成分のサイズを取得"""return -self.parent[self.root(x)]def all_sizes(self) -> List[int]:"""全連結成分のサイズのリストを取得 O(N)"""sizes = []for i in range(self.n):size = self.parent[i]if size < 0:sizes.append(-size)return sizesdef groups(self) -> List[List[int]]:"""全連結成分の内容のリストを取得 O(N・α(N))"""groups = dict()for i in range(self.n):p = self.root(i)if not groups.get(p):groups[p] = []groups[p].append(i)return list(groups.values())def group_count(self) -> int:"""連結成分の数を取得 O(1)"""return self.__group_count # 変数を返すだけなので、O(1)です###素因数分解###def prime_factorize(n: int) -> list:return_list = []while n % 2 == 0:return_list.append(2)n //= 2f = 3while f * f <= n:if n % f == 0:return_list.append(f)n //= felse:f += 2if n != 1:return_list.append(n)return return_list###n進数から10進数変換###def base_10(num_n,n):num_10 = 0for s in str(num_n):num_10 *= nnum_10 += int(s)return num_10###10進数からn進数変換###def base_n(num_10,n):str_n = ''while num_10:if num_10%n>=10:return -1str_n += str(num_10%n)num_10 //= nreturn int(str_n[::-1])###複数の数の最大公約数、最小公倍数###from functools import reduce# 最大公約数def gcd_list(num_list: list) -> int:return reduce(gcd, num_list)# 最小公倍数def lcm_base(x: int, y: int) -> int:return (x * y) // gcd(x, y)def lcm_list(num_list: list):return reduce(lcm_base, num_list, 1)###約数列挙###def make_divisors(n):lower_divisors, upper_divisors = [], []i = 1while i * i <= n:if n % i == 0:lower_divisors.append(i)if i != n // i:upper_divisors.append(n//i)i += 1return lower_divisors + upper_divisors[::-1]###順列###def nPr(n, r):npr = 1for i in range(n, n-r, -1):npr *= ireturn npr###組合せ###def nCr(n, r):factr = 1r = min(r, n - r)for i in range(r, 1, -1):factr *= ireturn nPr(n, r)//factr###組合せMOD###def comb(n,k):nCk = 1MOD = 998244353for i in range(n-k+1, n+1):nCk *= inCk %= MODfor i in range(1,k+1):nCk *= pow(i,MOD-2,MOD)nCk %= MODreturn nCk###回転行列###def RotationMatrix(before_x, before_y, d):d = math.radians(d)new_x = before_x * math.cos(d) - before_y * math.sin(d)new_y = before_x * math.sin(d) + before_y * math.cos(d)return new_x, new_y###ダイクストラ###def daikusutora(N, G, s):dist = [INF] * Nque = [(0, s)]dist[s] = 0while que:c, v = heappop(que)if dist[v] < c:continuefor t, cost in G[v]:if dist[v] + cost < dist[t]:dist[t] = dist[v] + costheappush(que, (dist[t], t))return distimport sys, refrom fractions import Fractionfrom math import ceil, floor, sqrt, pi, factorial, gcdfrom copy import deepcopyfrom collections import Counter, deque, defaultdictfrom heapq import heapify, heappop, heappushfrom itertools import accumulate, product, combinations, combinations_with_replacement, permutationsfrom bisect import bisect, bisect_left, bisect_rightfrom functools import reduce, lru_cachefrom decimal import Decimal, getcontext, ROUND_HALF_UPdef i_input(): return int(input())def i_map(): return map(int, input().split())def i_list(): return list(i_map())def i_row(N): return [i_input() for _ in range(N)]def i_row_list(N): return [i_list() for _ in range(N)]def s_input(): return input()def s_map(): return input().split()def s_list(): return list(s_map())def s_row(N): return [s_input for _ in range(N)]def s_row_str(N): return [s_list() for _ in range(N)]def s_row_list(N): return [list(s_input()) for _ in range(N)]def lcm(a, b): return a * b // gcd(a, b)def get_distance(x1, y1, x2, y2):d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)return ddef rotate(table):n_fild = []for x in zip(*table[::-1]):n_fild.append(x)return n_fildsys.setrecursionlimit(10 ** 7)INF = float('inf')MOD = 10 ** 9 + 7MOD2 = 998244353alpa = 'abcdefghijklmnopqrstuvwxyz'ALPA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'#input = sys.stdin.readlinedef main():N, P = i_map()nums = prime_factorize(P)invp = [0] * (N+1)invp[0] = 1count = [0] * (N+1)for i in range(1, N+1):p = prime_factorize(i)invp[i] = invp[i-1] * i % MODfor j in range(len(p)):count[p[j]] += 1p = INFfor i in range(len(nums)):p = min(p, count[nums[i]])A = pow(invp[-1], invp[-1], MOD)print(p * A % MOD)if __name__ == '__main__':main()