結果

問題 No.2857 Div Array
ユーザー LyricalMaestro
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 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()
0