結果
問題 |
No.681 Fractal Gravity Glue
|
ユーザー |
![]() |
提出日時 | 2025-06-12 19:47:04 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,228 bytes |
コンパイル時間 | 429 ms |
コンパイル使用メモリ | 82,052 KB |
実行使用メモリ | 849,648 KB |
最終ジャッジ日時 | 2025-06-12 19:47:10 |
合計ジャッジ時間 | 5,182 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 MLE * 1 -- * 11 |
ソースコード
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()