結果
問題 | No.2487 Multiple of M |
ユーザー | prin_kemkem |
提出日時 | 2023-09-29 23:43:20 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,844 bytes |
コンパイル時間 | 317 ms |
コンパイル使用メモリ | 87,176 KB |
実行使用メモリ | 82,316 KB |
最終ジャッジ日時 | 2023-09-30 12:52:19 |
合計ジャッジ時間 | 12,191 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 179 ms
81,144 KB |
testcase_01 | AC | 174 ms
81,524 KB |
testcase_02 | AC | 174 ms
81,368 KB |
testcase_03 | AC | 174 ms
81,388 KB |
testcase_04 | WA | - |
testcase_05 | AC | 174 ms
81,472 KB |
testcase_06 | AC | 177 ms
81,500 KB |
testcase_07 | AC | 173 ms
81,340 KB |
testcase_08 | AC | 174 ms
81,376 KB |
testcase_09 | AC | 172 ms
81,388 KB |
testcase_10 | AC | 172 ms
81,400 KB |
testcase_11 | AC | 175 ms
81,888 KB |
testcase_12 | AC | 176 ms
81,688 KB |
testcase_13 | AC | 175 ms
81,536 KB |
testcase_14 | AC | 175 ms
81,652 KB |
testcase_15 | AC | 177 ms
81,564 KB |
testcase_16 | AC | 177 ms
81,416 KB |
testcase_17 | AC | 175 ms
81,204 KB |
testcase_18 | AC | 177 ms
81,380 KB |
testcase_19 | AC | 179 ms
81,412 KB |
testcase_20 | AC | 177 ms
81,648 KB |
testcase_21 | AC | 175 ms
81,308 KB |
testcase_22 | AC | 173 ms
81,436 KB |
testcase_23 | AC | 174 ms
81,172 KB |
testcase_24 | AC | 173 ms
81,224 KB |
testcase_25 | AC | 183 ms
81,668 KB |
testcase_26 | AC | 182 ms
81,672 KB |
testcase_27 | AC | 175 ms
81,540 KB |
testcase_28 | AC | 179 ms
81,540 KB |
testcase_29 | WA | - |
testcase_30 | AC | 183 ms
81,620 KB |
testcase_31 | AC | 183 ms
81,620 KB |
testcase_32 | AC | 174 ms
81,240 KB |
testcase_33 | AC | 177 ms
81,652 KB |
testcase_34 | AC | 181 ms
81,748 KB |
testcase_35 | AC | 180 ms
81,744 KB |
testcase_36 | AC | 181 ms
81,256 KB |
testcase_37 | AC | 181 ms
81,744 KB |
testcase_38 | AC | 176 ms
81,576 KB |
testcase_39 | AC | 176 ms
81,640 KB |
testcase_40 | AC | 175 ms
81,680 KB |
testcase_41 | AC | 180 ms
82,316 KB |
testcase_42 | AC | 183 ms
81,652 KB |
testcase_43 | AC | 184 ms
81,920 KB |
testcase_44 | AC | 179 ms
81,732 KB |
testcase_45 | AC | 179 ms
81,628 KB |
testcase_46 | AC | 188 ms
81,520 KB |
testcase_47 | AC | 177 ms
81,852 KB |
testcase_48 | AC | 174 ms
81,472 KB |
testcase_49 | AC | 174 ms
81,640 KB |
testcase_50 | AC | 179 ms
81,880 KB |
testcase_51 | AC | 175 ms
81,196 KB |
testcase_52 | AC | 174 ms
81,264 KB |
testcase_53 | AC | 175 ms
81,440 KB |
testcase_54 | AC | 175 ms
81,216 KB |
testcase_55 | AC | 175 ms
81,436 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) 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): d = 1 for p, e in s.items(): d *= p**min(PM[p], e*(i+1)) l = M//d 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: 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(0) 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])