結果
問題 | No.2487 Multiple of M |
ユーザー | prin_kemkem |
提出日時 | 2023-09-30 00:20:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 198 ms / 2,000 ms |
コード長 | 4,116 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 86,900 KB |
実行使用メモリ | 81,500 KB |
最終ジャッジ日時 | 2023-09-30 12:53:06 |
合計ジャッジ時間 | 13,072 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 188 ms
80,556 KB |
testcase_01 | AC | 189 ms
80,696 KB |
testcase_02 | AC | 187 ms
80,664 KB |
testcase_03 | AC | 191 ms
80,712 KB |
testcase_04 | AC | 190 ms
80,736 KB |
testcase_05 | AC | 189 ms
80,808 KB |
testcase_06 | AC | 186 ms
80,624 KB |
testcase_07 | AC | 188 ms
80,464 KB |
testcase_08 | AC | 188 ms
80,708 KB |
testcase_09 | AC | 192 ms
80,584 KB |
testcase_10 | AC | 193 ms
80,492 KB |
testcase_11 | AC | 190 ms
81,028 KB |
testcase_12 | AC | 194 ms
81,028 KB |
testcase_13 | AC | 189 ms
80,940 KB |
testcase_14 | AC | 190 ms
81,048 KB |
testcase_15 | AC | 197 ms
80,956 KB |
testcase_16 | AC | 198 ms
81,024 KB |
testcase_17 | AC | 189 ms
80,860 KB |
testcase_18 | AC | 190 ms
81,036 KB |
testcase_19 | AC | 189 ms
81,024 KB |
testcase_20 | AC | 190 ms
81,120 KB |
testcase_21 | AC | 189 ms
80,568 KB |
testcase_22 | AC | 190 ms
80,712 KB |
testcase_23 | AC | 190 ms
80,796 KB |
testcase_24 | AC | 185 ms
80,552 KB |
testcase_25 | AC | 191 ms
80,952 KB |
testcase_26 | AC | 190 ms
80,928 KB |
testcase_27 | AC | 186 ms
81,088 KB |
testcase_28 | AC | 185 ms
80,964 KB |
testcase_29 | AC | 190 ms
80,972 KB |
testcase_30 | AC | 190 ms
81,092 KB |
testcase_31 | AC | 191 ms
81,008 KB |
testcase_32 | AC | 189 ms
80,632 KB |
testcase_33 | AC | 189 ms
81,116 KB |
testcase_34 | AC | 191 ms
81,004 KB |
testcase_35 | AC | 189 ms
81,004 KB |
testcase_36 | AC | 190 ms
80,512 KB |
testcase_37 | AC | 192 ms
80,828 KB |
testcase_38 | AC | 194 ms
80,940 KB |
testcase_39 | AC | 191 ms
81,024 KB |
testcase_40 | AC | 193 ms
80,944 KB |
testcase_41 | AC | 192 ms
81,500 KB |
testcase_42 | AC | 195 ms
81,116 KB |
testcase_43 | AC | 191 ms
80,992 KB |
testcase_44 | AC | 190 ms
81,268 KB |
testcase_45 | AC | 191 ms
81,132 KB |
testcase_46 | AC | 190 ms
81,012 KB |
testcase_47 | AC | 192 ms
81,088 KB |
testcase_48 | AC | 192 ms
81,032 KB |
testcase_49 | AC | 193 ms
80,844 KB |
testcase_50 | AC | 188 ms
81,036 KB |
testcase_51 | AC | 189 ms
80,792 KB |
testcase_52 | AC | 188 ms
80,576 KB |
testcase_53 | AC | 187 ms
80,740 KB |
testcase_54 | AC | 190 ms
80,668 KB |
testcase_55 | AC | 189 ms
80,668 KB |
ソースコード
from collections import defaultdict, deque, Counter import copy from itertools import combinations, permutations, product, accumulate, groupby, chain from heapq import heapify, heappop, heappush import math import bisect from pprint import pprint from random import randint import sys # sys.setrecursionlimit(700000) input = lambda: sys.stdin.readline().rstrip('\n') inf = float('inf') mod1 = 10**9+7 mod2 = 998244353 def ceil_div(x, y): return -(-x//y) ################################################# class Matrix(): def __init__(self, mat, mod=None): self.mat = mat self.n = len(mat) self.m = len(mat[0]) self.mod = mod def __mul__(self, other): ret = Matrix([[0]*other.m for _ in range(self.n)], self.mod) for i in range(self.n): for j in range(other.m): for k in range(self.m): ret[i][j] += self.mat[i][k]*other.mat[k][j] if self.mod is not None: ret[i][j] %= self.mod return ret def __add__(self, other): ret = Matrix([[self.mat[i][j] for j in range(self.m)] for i in range(self.n)], self.mod) for i in range(other.n): for j in range(other.m): ret[i][j] += other.mat[i][j] if self.mod is not None: ret[i][j] %= self.mod return ret def __sub__(self, other): ret = Matrix([[self.mat[i][j] for j in range(self.m)] for i in range(self.n)], self.mod) for i in range(other.n): for j in range(other.m): ret[i][j] -= other.mat[i][j] if self.mod is not None: ret[i][j] %= self.mod return ret def __pow__(self, scalar): a = Matrix([[self.mat[i][j] for j in range(self.m)] for i in range(self.n)], self.mod) ret = Matrix.e(self.n, self.mod) while scalar: if scalar&1: ret *= a a *= a scalar >>= 1 return ret def scalar_mul(self, a): ret = Matrix([[self.mat[i][j] for j in range(self.m)] for i in range(self.n)], self.mod) for i in range(self.n): for j in range(self.m): ret[i][j] *= a if self.mod is not None: ret[i][j] %= self.mod return ret def __repr__(self) -> str: return self.mat.__repr__() def __getitem__(self, i): return self.mat[i] def __setitem__(self, i, x): self.mat[i] = x def __len__(self): return len(self.mat) def t(self): return Matrix([list(column) for column in zip(*self.mat)], self.mod) def turn(matrix): if type(matrix) != 'Matrix': return Matrix([list(column) for column in zip(*matrix)]) return Matrix([list(column) for column in zip(*matrix.mat)], matrix.mod) def e(size, mod): return Matrix([[i == j for j in range(size)] for i in range(size)], mod) def prime_factorize(n): ret = defaultdict(int) i = 2 while i*i <= n: if n%i == 0: ret[i] += 1 n //= i else: i += 1 if n != 1: ret[n] += 1 return ret N, M, K = map(int, input().split()) a = Matrix([[0], [1]], mod=mod2) if K == 1: d = 1 l = M A = Matrix([[d-1, d*(l-1)%mod2], [d, (d-1+d*(l-2))%mod2]], mod=mod2) a = A**(N-1) * a print(a[0][0]) exit() PM, PK = prime_factorize(M), prime_factorize(K) x = 0 s = {} for p, e in PM.items(): if PK[p] == 0: continue s[p] = PK[p] x = max(x, ceil_div(e, PK[p])) i = 0 while i < min(x, N-1): d = 1 for p, e in s.items(): d *= p**min(PM[p], e*(i+1)) l = M//d if l == 1: print(a[0][0]*pow(M-1, N-1-i, mod2)%mod2) exit() A = Matrix([[d-1, d*(l-1)%mod2], [d, (d-1+d*(l-2))%mod2]], mod=mod2) a = A*a i += 1 if i == N-1: print(a[0][0]) exit() d = 1 for p, e in s.items(): d *= p**min(PM[p], e*(i+1)) l = M//d if l == 1: print(a[0][0]*pow(M-1, N-1-i, mod2)%mod2) else: A = Matrix([[d-1, d*(l-1)%mod2], [d, (d-1+d*(l-2))%mod2]], mod=mod2) a = A**(N-1-i) * a print(a[0][0])