結果
問題 | No.2487 Multiple of M |
ユーザー | prin_kemkem |
提出日時 | 2023-09-30 00:04:46 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,062 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 87,212 KB |
実行使用メモリ | 81,456 KB |
最終ジャッジ日時 | 2023-09-30 12:52:49 |
合計ジャッジ時間 | 12,965 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 192 ms
80,464 KB |
testcase_01 | AC | 191 ms
80,764 KB |
testcase_02 | AC | 189 ms
80,852 KB |
testcase_03 | AC | 190 ms
80,680 KB |
testcase_04 | AC | 190 ms
80,588 KB |
testcase_05 | AC | 189 ms
80,800 KB |
testcase_06 | AC | 189 ms
80,572 KB |
testcase_07 | AC | 189 ms
80,624 KB |
testcase_08 | AC | 187 ms
80,920 KB |
testcase_09 | AC | 190 ms
80,696 KB |
testcase_10 | AC | 188 ms
80,600 KB |
testcase_11 | AC | 187 ms
80,836 KB |
testcase_12 | AC | 190 ms
80,944 KB |
testcase_13 | AC | 192 ms
81,016 KB |
testcase_14 | AC | 189 ms
81,044 KB |
testcase_15 | AC | 190 ms
81,096 KB |
testcase_16 | AC | 189 ms
81,292 KB |
testcase_17 | AC | 188 ms
80,724 KB |
testcase_18 | AC | 190 ms
80,912 KB |
testcase_19 | AC | 189 ms
80,940 KB |
testcase_20 | AC | 188 ms
80,996 KB |
testcase_21 | AC | 188 ms
80,784 KB |
testcase_22 | AC | 188 ms
80,856 KB |
testcase_23 | AC | 191 ms
80,820 KB |
testcase_24 | AC | 189 ms
80,804 KB |
testcase_25 | AC | 190 ms
81,112 KB |
testcase_26 | AC | 188 ms
81,012 KB |
testcase_27 | AC | 192 ms
81,060 KB |
testcase_28 | AC | 191 ms
81,008 KB |
testcase_29 | WA | - |
testcase_30 | AC | 191 ms
80,952 KB |
testcase_31 | AC | 193 ms
80,980 KB |
testcase_32 | AC | 189 ms
80,540 KB |
testcase_33 | AC | 189 ms
80,960 KB |
testcase_34 | AC | 187 ms
81,152 KB |
testcase_35 | AC | 191 ms
81,004 KB |
testcase_36 | AC | 192 ms
80,648 KB |
testcase_37 | AC | 191 ms
81,260 KB |
testcase_38 | AC | 192 ms
81,040 KB |
testcase_39 | AC | 191 ms
80,980 KB |
testcase_40 | AC | 189 ms
81,164 KB |
testcase_41 | AC | 190 ms
81,456 KB |
testcase_42 | AC | 190 ms
80,940 KB |
testcase_43 | AC | 191 ms
80,832 KB |
testcase_44 | AC | 189 ms
81,032 KB |
testcase_45 | AC | 191 ms
81,064 KB |
testcase_46 | AC | 190 ms
81,084 KB |
testcase_47 | AC | 192 ms
81,036 KB |
testcase_48 | AC | 191 ms
81,156 KB |
testcase_49 | AC | 191 ms
81,052 KB |
testcase_50 | AC | 189 ms
81,068 KB |
testcase_51 | AC | 187 ms
80,660 KB |
testcase_52 | AC | 188 ms
80,808 KB |
testcase_53 | AC | 188 ms
80,500 KB |
testcase_54 | AC | 187 ms
80,484 KB |
testcase_55 | AC | 185 ms
80,664 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]) 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]) 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])