結果
問題 |
No.681 Fractal Gravity Glue
|
ユーザー |
![]() |
提出日時 | 2025-05-14 12:56:30 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,623 bytes |
コンパイル時間 | 176 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 849,088 KB |
最終ジャッジ日時 | 2025-05-14 12:58:47 |
合計ジャッジ時間 | 3,817 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 MLE * 1 -- * 11 |
ソースコード
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()