結果
問題 | No.2857 Div Array |
ユーザー |
![]() |
提出日時 | 2024-08-25 15:45:39 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,443 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 82,524 KB |
実行使用メモリ | 119,980 KB |
最終ジャッジ日時 | 2024-08-25 15:45:46 |
合計ジャッジ時間 | 7,240 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 TLE * 2 -- * 18 |
ソースコード
from collections import defaultdict, deque, Counter# from functools import cache# import copyfrom itertools import combinations, permutations, product, accumulate, groupby, chain# from more_itertools import distinct_permutationsfrom heapq import heapify, heappop, heappushimport mathimport bisectfrom pprint import pprintfrom random import randint, shuffle, randrangeimport sys# sys.setrecursionlimit(200000)input = lambda: sys.stdin.readline().rstrip('\n')inf = float('inf')mod1 = 10**9+7mod2 = 998244353def ceil_div(x, y): return -(-x//y)#################################################class Matrix():def __init__(self, mat, mod=None):self.mat = matself.n = len(mat)self.m = len(mat[0])self.mod = moddef __mul__(self, other):ret = Matrix([[0]*other.m for _ in range(self.n)], self.mod)other_t = other.t()for i in range(self.n):s = self.mat[i]for j in range(other.m):o = other_t.mat[j]for k in range(self.m):ret[i][j] += s[k]*o[k]if self.mod is not None: ret[i][j] %= self.modreturn retdef __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.modreturn retdef __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.modreturn retdef __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 *= aa *= ascalar >>= 1return retdef 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] *= aif self.mod is not None: ret[i][j] %= self.modreturn retdef __repr__(self) -> str:return self.mat.__repr__()def __getitem__(self, i):return self.mat[i]def __setitem__(self, i, x):self.mat[i] = xdef __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())A = [[False]*(M+1) for _ in range(M+1)]div = [0]+[M//i for i in range(1, M+1)]for i in range(1, M+1):for j in range(1, M+1):A[i][j] = abs(div[i] - div[j]) <= Kdp = [[0]+[1]*M]dp = Matrix(dp, mod2)A = Matrix(A, mod2)dp = dp*A**(N-1)ans = 0for a in dp[0]:ans += aans %= mod2print(ans)