結果

問題 No.2017 Mod7 Parade
ユーザー lam6er
提出日時 2025-03-20 18:46:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 146 ms / 2,000 ms
コード長 1,665 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 106,676 KB
最終ジャッジ日時 2025-03-20 18:47:33
合計ジャッジ時間 3,625 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    K = int(data[idx])
    idx += 1
    
    inv9_mod7 = 4  # 9^(-1) mod7
    
    elements = []
    for _ in range(K):
        D = int(data[idx])
        idx += 1
        L = int(data[idx])
        idx += 1
        
        if D == 0:
            x_mod7 = 0
            pow10_L_mod7 = 1
            for _ in range(L % 6):
                pow10_L_mod7 = (pow10_L_mod7 * 10) % 7
        else:
            exponent = L % 6
            if exponent == 0:
                exponent = 6
            pow10_L = pow(10, exponent, 7)
            numerator = (pow10_L - 1) % 7
            x_mod7 = (D * numerator * inv9_mod7) % 7
        
        pow10_len_i = 1
        exponent_L = L % 6
        if exponent_L == 0 and L != 0:
            exponent_L = 6
        pow10_len_i = pow(10, exponent_L, 7)
        
        elements.append((x_mod7, pow10_len_i))
    
    prev_dp = [0] * 7
    ans = 0
    
    for x_mod7, pow10_len_i in elements:
        temp_dp = [0] * 7
        
        for m_prev in range(7):
            if prev_dp[m_prev]:
                new_m = (m_prev * pow10_len_i + x_mod7) % 7
                temp_dp[new_m] = (temp_dp[new_m] + prev_dp[m_prev]) % MOD
        
        temp_dp[x_mod7] = (temp_dp[x_mod7] + 1) % MOD
        
        current_sum = 0
        for m in range(7):
            current_sum = (current_sum + m * temp_dp[m]) % MOD
        
        ans = (ans + current_sum) % MOD
        
        for m in range(7):
            prev_dp[m] = (prev_dp[m] + temp_dp[m]) % MOD
    
    print(ans % MOD)

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