結果

問題 No.681 Fractal Gravity Glue
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:45:43
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,228 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 849,548 KB
最終ジャッジ日時 2025-06-12 14:47:30
合計ジャッジ時間 5,711 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 MLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 10**9 + 7

def main():
    sys.setrecursionlimit(1 << 25)
    n = int(sys.stdin.readline().strip())
    b_d = sys.stdin.readline().strip().split()
    b = int(b_d[0])
    d = int(b_d[1])

    if b == 0:
        print(0)
        return

    # Compute S_total = S(b, d)
    def compute_S(b, d):
        if b == 1:
            return d % MOD
        h = pow(d + 1, b, MOD)
        h = (h - 1) % MOD
        term1 = ( (d + 1) % MOD ) * h % MOD
        inv_d = pow(d, MOD - 2, MOD)
        term1 = term1 * inv_d % MOD
        term2 = (b) % MOD
        S = (term1 - term2) % MOD
        return S

    S_total = compute_S(b, d)

    # Compute sum(n, b, d)
    from functools import lru_cache
    import math

    @lru_cache(maxsize=None)
    def sum_layers(n, b, d):
        if b == 1:
            return min(n, d) % MOD
        if d == 0:
            return 0

        # Check if h = (d+1)^(b-1) -1 > n
        # Compute (d+1)^(b-1) > n+1
        if d + 1 == 1:
            h = 0
        else:
            log_d_plus_1 = math.log(d + 1)
            log_n_plus_1 = math.log(n + 1)
            if (b - 1) * log_d_plus_1 > log_n_plus_1 + 1e-12:
                return sum_layers(n, b - 1, d)

        # Else, compute h = (d+1)^(b-1) -1
        h = pow(d + 1, b - 1, MOD)
        h = (h - 1) % MOD

        # Compute k = min(d, n // (h+1))
        k = n // (h + 1)
        if k > d:
            k = d

        rem = n - k * (h + 1)

        # Compute S(b-1, d)
        h_b_minus_1 = pow(d + 1, b - 1, MOD)
        h_b_minus_1 = (h_b_minus_1 - 1) % MOD
        term1 = ( (d + 1) % MOD ) * h_b_minus_1 % MOD
        inv_d = pow(d, MOD - 2, MOD)
        term1 = term1 * inv_d % MOD
        term2 = (b - 1) % MOD
        S_b_minus_1_d = (term1 - term2) % MOD

        sum_total = (k * ( (S_b_minus_1_d + b) % MOD )) % MOD

        if rem > 0:
            if k < d:
                sum_rem = sum_layers(rem, b - 1, d)
            else:
                sum_rem = sum_layers(rem, b - 1, d)
            sum_total = (sum_total + sum_rem) % MOD

        return sum_total % MOD

    sum_n = sum_layers(n, b, d) % MOD

    # Compute result
    result = (S_total - sum_n) % MOD
    print(result)

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