結果
| 問題 |
No.2857 Div Array
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2025-09-27 02:52:54 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 146 ms / 2,000 ms |
| コード長 | 1,778 bytes |
| コンパイル時間 | 413 ms |
| コンパイル使用メモリ | 82,820 KB |
| 実行使用メモリ | 76,676 KB |
| 最終ジャッジ日時 | 2025-09-27 02:52:59 |
| 合計ジャッジ時間 | 4,473 ms |
|
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
# https://yukicoder.me/problems/no/2857
from collections import deque
MOD = 998244353
def prd1(matrix, left_array, matrix_size):
ans_array = [0] * matrix_size
for i in range(matrix_size):
for j in range(matrix_size):
ans_array[i] += (matrix[i][j] * left_array[j]) % MOD
ans_array[i] %= MOD
return ans_array
def prd2(matrix1, matrix2, matrix_size):
ans_matrix = [[0] * matrix_size for _ in range(matrix_size)]
for i in range(matrix_size):
for j in range(matrix_size):
for k in range(matrix_size):
ans_matrix[i][j] += (matrix1[i][k] * matrix2[k][j]) % MOD
ans_matrix[i][j] %= MOD
return ans_matrix
def main():
N, M, K = map(int, input().split())
base_array_map = {}
for i in range(1, M + 1):
a = M // i
if a not in base_array_map:
base_array_map[a] = 0
base_array_map[a] += 1
cost_array = [(key, value ) for key, value in base_array_map.items()]
cost_array.sort()
key_array = [key for key, _ in cost_array]
cost_array = [cost for _, cost in cost_array]
matrix_size = len(cost_array)
matrix = [[0] * matrix_size for _ in range(matrix_size)]
for i in range(matrix_size):
for j in range(matrix_size):
if abs(key_array[i]- key_array[j]) <= K:
matrix[i][j] = cost_array[i]
ans_array = cost_array * matrix_size
N -= 1
while N > 0:
if N % 2 == 1:
ans_array = prd1(matrix, ans_array, matrix_size)
matrix = prd2(matrix, matrix, matrix_size)
N //= 2
answer = 0
for i in range(matrix_size):
answer += ans_array[i]
answer %= MOD
print(answer)
if __name__ == "__main__":
main()