結果

問題 No.1407 Kindness
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:39:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 400 ms / 2,000 ms
コード長 1,911 bytes
コンパイル時間 240 ms
コンパイル使用メモリ 82,732 KB
実行使用メモリ 78,024 KB
最終ジャッジ日時 2025-03-20 20:39:22
合計ジャッジ時間 6,472 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 10**9 + 7

def main():
    N = input().strip()
    ns = [int(c) for c in N]
    K = len(ns)
    
    sum_less = 0
    if K > 1:
        inv_44 = pow(44, mod-2, mod)
        numerator = (pow(45, K-1, mod) - 1) % mod
        sum_less = (45 * numerator) % mod
        sum_less = (sum_less * inv_44) % mod
    
    def compute_sum_k():
        from collections import defaultdict

        dp = defaultdict(lambda: (0, 0))  # (sum, cnt)
        dp[(0, True, True)] = (0, 0)

        for pos in range(K):
            new_dp = defaultdict(lambda: (0, 0))
            for (p, tight, lz), (sum_prev, cnt_prev) in dp.items():
                if p != pos:
                    continue
                current_digit = ns[pos]
                d_max = current_digit if tight else 9
                for d in range(0, d_max + 1):
                    new_tight = tight and (d == current_digit)
                    new_lz = lz

                    if lz:
                        if d == 0:
                            continue
                        new_lz = False
                        new_sum = d
                        new_cnt = 1
                    else:
                        if d == 0:
                            continue
                        new_sum = (sum_prev * d) % mod
                        new_cnt = cnt_prev

                    key = (pos + 1, new_tight, new_lz)
                    curr_s, curr_c = new_dp[key]
                    curr_s = (curr_s + new_sum) % mod
                    curr_c = (curr_c + new_cnt) % mod
                    new_dp[key] = (curr_s, curr_c)
            dp = new_dp

        sum_k = 0
        for (p, tight, lz), (sum_val, _) in dp.items():
            if p == K and not lz:
                sum_k = (sum_k + sum_val) % mod
        return sum_k

    sum_k = compute_sum_k()
    answer = (sum_less + sum_k) % mod
    print(answer)

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