結果

問題 No.1631 Sorting Integers (Multiple of K) Easy
ユーザー gew1fw
提出日時 2025-06-12 16:07:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 893 bytes
コンパイル時間 393 ms
コンパイル使用メモリ 82,044 KB
実行使用メモリ 380,940 KB
最終ジャッジ日時 2025-06-12 16:07:14
合計ジャッジ時間 5,845 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

from functools import lru_cache

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    counts = list(map(int, input[idx:idx + 9]))
    idx += 9
    counts_tuple = tuple(counts)
    
    @lru_cache(maxsize=None)
    def dp(remainder, counts):
        if all(c == 0 for c in counts):
            return 1 if remainder == 0 else 0
        total = 0
        for i in range(9):
            if counts[i] == 0:
                continue
            new_counts = list(counts)
            new_counts[i] -= 1
            new_counts_tuple = tuple(new_counts)
            new_remainder = (remainder * 10 + (i + 1)) % K
            total += dp(new_remainder, new_counts_tuple)
        return total
    
    print(dp(0, counts_tuple))

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