結果
問題 | No.2487 Multiple of M |
ユーザー | prin_kemkem |
提出日時 | 2023-09-29 23:56:07 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,050 bytes |
コンパイル時間 | 471 ms |
コンパイル使用メモリ | 87,232 KB |
実行使用メモリ | 81,492 KB |
最終ジャッジ日時 | 2023-09-30 12:52:48 |
合計ジャッジ時間 | 12,157 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 180 ms
80,780 KB |
testcase_01 | AC | 177 ms
80,696 KB |
testcase_02 | AC | 173 ms
80,612 KB |
testcase_03 | AC | 177 ms
80,716 KB |
testcase_04 | AC | 178 ms
80,340 KB |
testcase_05 | AC | 173 ms
80,672 KB |
testcase_06 | AC | 176 ms
80,864 KB |
testcase_07 | AC | 170 ms
80,640 KB |
testcase_08 | AC | 174 ms
80,676 KB |
testcase_09 | AC | 172 ms
80,652 KB |
testcase_10 | AC | 169 ms
80,392 KB |
testcase_11 | AC | 176 ms
81,200 KB |
testcase_12 | AC | 172 ms
80,932 KB |
testcase_13 | AC | 171 ms
81,256 KB |
testcase_14 | AC | 173 ms
81,172 KB |
testcase_15 | AC | 175 ms
81,068 KB |
testcase_16 | AC | 177 ms
80,976 KB |
testcase_17 | AC | 174 ms
80,780 KB |
testcase_18 | AC | 172 ms
80,888 KB |
testcase_19 | AC | 176 ms
81,064 KB |
testcase_20 | AC | 174 ms
81,184 KB |
testcase_21 | AC | 177 ms
80,492 KB |
testcase_22 | AC | 180 ms
80,600 KB |
testcase_23 | AC | 173 ms
80,824 KB |
testcase_24 | AC | 172 ms
80,316 KB |
testcase_25 | AC | 175 ms
80,888 KB |
testcase_26 | AC | 186 ms
81,180 KB |
testcase_27 | AC | 177 ms
81,072 KB |
testcase_28 | AC | 174 ms
80,968 KB |
testcase_29 | WA | - |
testcase_30 | AC | 184 ms
80,940 KB |
testcase_31 | AC | 179 ms
81,084 KB |
testcase_32 | AC | 173 ms
80,688 KB |
testcase_33 | AC | 177 ms
80,764 KB |
testcase_34 | AC | 177 ms
80,992 KB |
testcase_35 | AC | 177 ms
80,916 KB |
testcase_36 | AC | 181 ms
80,884 KB |
testcase_37 | AC | 177 ms
80,988 KB |
testcase_38 | AC | 176 ms
81,076 KB |
testcase_39 | AC | 181 ms
81,180 KB |
testcase_40 | AC | 182 ms
80,888 KB |
testcase_41 | AC | 178 ms
81,492 KB |
testcase_42 | AC | 178 ms
81,008 KB |
testcase_43 | AC | 180 ms
80,892 KB |
testcase_44 | AC | 178 ms
81,020 KB |
testcase_45 | AC | 176 ms
81,068 KB |
testcase_46 | AC | 176 ms
80,972 KB |
testcase_47 | AC | 174 ms
81,076 KB |
testcase_48 | AC | 175 ms
81,236 KB |
testcase_49 | AC | 176 ms
80,756 KB |
testcase_50 | AC | 176 ms
80,940 KB |
testcase_51 | AC | 172 ms
80,748 KB |
testcase_52 | AC | 174 ms
80,632 KB |
testcase_53 | AC | 172 ms
80,596 KB |
testcase_54 | AC | 172 ms
80,368 KB |
testcase_55 | AC | 176 ms
80,692 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(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(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])