結果
問題 | No.2487 Multiple of M |
ユーザー | prin_kemkem |
提出日時 | 2023-09-29 22:45:05 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,159 bytes |
コンパイル時間 | 265 ms |
コンパイル使用メモリ | 87,144 KB |
実行使用メモリ | 81,684 KB |
最終ジャッジ日時 | 2023-09-30 12:52:07 |
合計ジャッジ時間 | 11,991 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 176 ms
81,404 KB |
testcase_01 | AC | 177 ms
81,204 KB |
testcase_02 | AC | 176 ms
81,516 KB |
testcase_03 | WA | - |
testcase_04 | AC | 173 ms
81,204 KB |
testcase_05 | AC | 176 ms
81,384 KB |
testcase_06 | AC | 174 ms
81,188 KB |
testcase_07 | AC | 172 ms
81,500 KB |
testcase_08 | AC | 173 ms
81,468 KB |
testcase_09 | AC | 173 ms
81,496 KB |
testcase_10 | AC | 170 ms
81,260 KB |
testcase_11 | AC | 172 ms
81,600 KB |
testcase_12 | AC | 172 ms
81,524 KB |
testcase_13 | AC | 172 ms
81,504 KB |
testcase_14 | AC | 175 ms
81,280 KB |
testcase_15 | AC | 175 ms
81,256 KB |
testcase_16 | AC | 177 ms
81,284 KB |
testcase_17 | AC | 174 ms
81,568 KB |
testcase_18 | AC | 175 ms
81,448 KB |
testcase_19 | AC | 172 ms
81,504 KB |
testcase_20 | AC | 176 ms
81,600 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | AC | 174 ms
81,516 KB |
testcase_32 | AC | 172 ms
81,288 KB |
testcase_33 | AC | 173 ms
81,512 KB |
testcase_34 | AC | 182 ms
81,420 KB |
testcase_35 | AC | 172 ms
81,416 KB |
testcase_36 | AC | 176 ms
81,492 KB |
testcase_37 | AC | 175 ms
81,484 KB |
testcase_38 | WA | - |
testcase_39 | AC | 175 ms
81,468 KB |
testcase_40 | AC | 172 ms
81,200 KB |
testcase_41 | AC | 173 ms
81,380 KB |
testcase_42 | AC | 177 ms
81,416 KB |
testcase_43 | AC | 176 ms
81,552 KB |
testcase_44 | AC | 177 ms
81,412 KB |
testcase_45 | AC | 178 ms
81,268 KB |
testcase_46 | AC | 173 ms
81,528 KB |
testcase_47 | AC | 175 ms
81,380 KB |
testcase_48 | AC | 177 ms
81,444 KB |
testcase_49 | AC | 178 ms
81,544 KB |
testcase_50 | WA | - |
testcase_51 | AC | 174 ms
81,520 KB |
testcase_52 | AC | 173 ms
81,520 KB |
testcase_53 | AC | 173 ms
81,416 KB |
testcase_54 | WA | - |
testcase_55 | AC | 173 ms
81,572 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) N, M, K = map(int, input().split()) d = math.gcd(M, K) M //= d; K //= d if M >= 2: a = Matrix([[0], [1]], mod=mod2) A = Matrix([[d-1, d*(M-1)%mod2], [d, (d-1+d*(M-2))%mod2]], mod=mod2) print((A**(N-1) * a)[0][0]) else: print(0)