結果

問題 No.681 Fractal Gravity Glue
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:32:42
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,623 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 81,828 KB
実行使用メモリ 849,084 KB
最終ジャッジ日時 2025-04-24 12:33:59
合計ジャッジ時間 3,609 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 MLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def modinv(a):
    return pow(a, MOD - 2, MOD)

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    b = int(input[1])
    d = int(input[2])
    
    if b == 0:
        print(0)
        return
    
    inv_d = modinv(d)
    a = d + 1
    
    # Calculate sum_b = ((a^(b+1) - a) / d) - b mod MOD
    numerator = (pow(a, b + 1, MOD) - a) % MOD
    sum_b = (numerator * inv_d) % MOD
    sum_b = (sum_b - b) % MOD
    
    if n == 0:
        print(sum_b % MOD)
        return
    
    # Function to compute s(n)
    def compute_s(n):
        s = 0
        stack = []
        stack.append((b, 1))  # (current_level, phase)
        
        while stack and n > 0:
            i, phase = stack.pop()
            
            if i == 1:
                add = min(n, d)
                s = (s + add) % MOD
                n -= add
                continue
            
            if phase == 1:
                # Check if h_prev >= n
                exponent = i - 1
                threshold = n + 1
                current = 1
                exceeds = False
                for _ in range(exponent):
                    if current > threshold // a:
                        exceeds = True
                        break
                    current *= a
                    if current > threshold:
                        exceeds = True
                        break
                if exceeds:
                    stack.append((i, 1))
                    stack.append((i - 1, 1))
                else:
                    h_prev = pow(a, exponent) - 1
                    sum_prev = ((pow(a, i, MOD) - a) * inv_d - (i - 1)) % MOD
                    s = (s + sum_prev) % MOD
                    n -= h_prev
                    if n <= 0:
                        break
                    stack.append((i, 2))
            elif phase == 2:
                h_prev = pow(a, i - 1) - 1
                sum_prev = ((pow(a, i, MOD) - a) * inv_d - (i - 1)) % MOD
                s_block = 1 + h_prev
                k = min(d, n // s_block)
                s = (s + k * i) % MOD
                s = (s + k * sum_prev) % MOD
                n -= k * s_block
                if n <= 0:
                    break
                if k < d:
                    if n >= 1:
                        s = (s + i) % MOD
                        n -= 1
                        if n <= 0:
                            break
                    stack.append((i - 1, 1))
        return s
    
    s = compute_s(n)
    answer = (sum_b - s) % MOD
    print(answer)

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