結果

問題 No.2857 Div Array
コンテスト
ユーザー LyricalMaestro
提出日時 2025-09-27 02:39:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,227 bytes
コンパイル時間 279 ms
コンパイル使用メモリ 82,844 KB
実行使用メモリ 76,792 KB
最終ジャッジ日時 2025-09-27 02:39:34
合計ジャッジ時間 6,336 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://yukicoder.me/problems/no/2857

from collections import deque

MOD = 998244353


def prd(left_map, right_map, K):
    ans_map = {}

    for l_key, l_value in left_map.items():
        for r_key, r_value in right_map.items():
            if abs(l_key[1] - r_key[0]) <= K:
                key = (l_key[0], r_key[1])
                if key not in ans_map:
                    ans_map[key] = 0
                ans_map[key] += (l_value * r_value) % MOD
                ans_map[key] %= MOD
    return ans_map




def main():
    N, M, K = map(int, input().split())

    base_array_map = {}
    for i in range(1, M + 1):
        a = M // i
        if (a, a) not in base_array_map:
            base_array_map[(a, a)] = 0
        base_array_map[(a, a)] += 1
    
    array_map = base_array_map.copy()
    ans_map = {}
    while N > 0:
        if N % 2 == 1:
            if len(ans_map) == 0:
                ans_map = array_map.copy()
            else:
                ans_map = prd(ans_map, array_map,K )

        array_map = prd(array_map, array_map, K)
        N //= 2

    answer = 0
    for value in ans_map.values():
        answer += value
        answer %= MOD
    print(answer)



if __name__ == "__main__":
    main()
0