結果
| 問題 | No.681 Fractal Gravity Glue |
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:25:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 9,007 bytes |
| コンパイル時間 | 1,389 ms |
| コンパイル使用メモリ | 103,088 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:27:08 |
| 合計ジャッジ時間 | 2,170 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <functional> // For std::function
using namespace std;
long long N_glob; // n (layers completed from bottom)
long long B_glob; // b (target beauty)
long long D_glob; // d (difficulty)
long long MOD = 1e9 + 7;
map<pair<long long, long long>, long long> memo;
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
long long modInverse(long long n) {
return power(n, MOD - 2);
}
long long D_inv_glob;
// Height of G_{beauty, d} modulo MOD
long long get_H_mod(long long beauty) {
if (beauty == 0) return 0;
long long term_pow = power(D_glob + 1, beauty);
return (term_pow - 1 + MOD) % MOD;
}
// Sum of stone sizes in G_{beauty, d} modulo MOD
long long get_S_mod(long long beauty) {
if (beauty == 0) return 0;
long long h_val_mod = get_H_mod(beauty);
long long term1_factor = (D_glob + 1) % MOD;
long long term1 = (term1_factor * h_val_mod) % MOD;
term1 = (term1 * D_inv_glob) % MOD;
long long s_val = (term1 - (beauty % MOD) + MOD) % MOD;
return s_val;
}
// True height of G_{beauty, d}, capped at limit. Used for comparisons.
long long get_H_true(long long beauty, long long limit) {
if (beauty == 0) return 0;
unsigned __int128 current_h = 0;
unsigned __int128 term_val = 1; // (D_glob+1)^0
// Calculate (D_glob+1)^beauty - 1 carefully to avoid overflow
// (D_glob+1)^beauty can be huge.
// Max beauty relevant for comparisons is ~60-70 for N_glob up to 10^9
if (D_glob == 0) return 0; // Problem says d > 0
unsigned __int128 d_plus_1 = D_glob + 1;
for (int i = 0; i < beauty; ++i) {
term_val *= d_plus_1;
if (term_val > limit + 1) { // +1 because H is term_val - 1
term_val = limit + 1; // Cap it
break;
}
}
current_h = term_val - 1;
if (current_h > limit) return limit;
return (long long)current_h;
}
function<long long(long long, long long)> actual_calc_recursive;
long long do_actual_calc_recursive(long long current_b, long long current_n_done) {
long long h_true_current_b = get_H_true(current_b, N_glob + 1);
if (current_n_done >= h_true_current_b) {
return 0;
}
if (current_b == 0) {
return 0;
}
if (current_b == 1) {
// G_{1,D_glob} has D_glob stones of size 1. Height D_glob.
long long remaining_stones = D_glob - current_n_done;
if (remaining_stones <= 0) return 0;
return remaining_stones % MOD; // Stone size is 1
}
if (memo.count({current_b, current_n_done})) {
return memo[{current_b, current_n_done}];
}
long long h_true_prev_b = get_H_true(current_b - 1, N_glob + 1);
long long s_mod_prev_b = get_S_mod(current_b - 1);
long long ans = 0;
// Case A: current_n_done < H_true(current_b - 1, D_glob)
if (current_n_done < h_true_prev_b) {
ans = actual_calc_recursive(current_b - 1, current_n_done);
long long sum_of_d_S_prev_b = (D_glob % MOD * s_mod_prev_b) % MOD;
long long sum_of_d_stones_curr_b = (D_glob % MOD * (current_b % MOD)) % MOD;
ans = (ans + sum_of_d_S_prev_b) % MOD;
ans = (ans + sum_of_d_stones_curr_b) % MOD;
}
// Case B: current_n_done >= H_true(current_b - 1, D_glob)
else {
long long h_unit_true = h_true_prev_b + 1; // True height of (G_{b-1,d}, stone_b)
if (h_unit_true == 0) { // Avoid division by zero if h_true_prev_b = -1 (or similar underflow for u_l_l)
// This should not happen if current_b > 1 and D_glob > 0
h_unit_true = N_glob + 2; // effectively infinite height, so q=0
}
long long q = current_n_done / h_unit_true;
long long n_rem_in_unit = current_n_done % h_unit_true;
if (q >= D_glob) { // All D_glob (G,S) pairs are passed. current_n_done is in final G block.
long long n_done_for_final_G = current_n_done - D_glob * h_unit_true;
ans = actual_calc_recursive(current_b - 1, n_done_for_final_G);
} else {
// current_n_done falls within the (q)-th G or S block (0-indexed q)
ans = actual_calc_recursive(current_b - 1, n_rem_in_unit);
// Check if G_q was fully built
if (n_rem_in_unit < h_true_prev_b) { // G_q not fully built
ans = (ans + current_b % MOD) % MOD; // Stone S_q (size current_b)
} else { // G_q fully built. Check S_q. n_rem_in_unit >= h_true_prev_b
// If n_rem_in_unit == h_true_prev_b, S_q is not built
if (n_rem_in_unit < h_unit_true) { // S_q not built (n_rem_in_unit == h_true_prev_b)
ans = (ans + current_b % MOD) % MOD;
}
// Else S_q is built (n_rem_in_unit >= h_unit_true, which means n_rem_in_unit covered G_q and S_q,
// but this case is num_full_units_built = q+1, not q)
// This means if n_rem_in_unit >= h_unit_true, it is effectively n_rem_in_unit = 0 for next unit.
// The q, n_rem logic handles this. If n_rem_in_unit == h_true_prev_b, S_q is unbuilt.
}
// Add remaining unbuilt parts
long long s_mod_prev_plus_k = (s_mod_prev_b + current_b % MOD + MOD) % MOD;
long long num_remaining_full_pairs = D_glob - 1 - q;
if (num_remaining_full_pairs > 0) {
ans = (ans + (num_remaining_full_pairs % MOD * s_mod_prev_plus_k) % MOD) % MOD;
}
ans = (ans + s_mod_prev_b) % MOD; // Final G_d block (G_{current_b-1, D_glob})
}
}
return memo[{current_b, current_n_done}] = ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N_glob >> B_glob >> D_glob;
if (D_glob == 0 && B_glob > 0) { // Should not happen per constraints d>0
cout << 0 << endl;
return 0;
}
if (B_glob == 0) {
cout << 0 << endl;
return 0;
}
D_inv_glob = modInverse(D_glob);
actual_calc_recursive = do_actual_calc_recursive; // Assign to std::function
// Determine k_eff_b: effective B for recursive calls, after peeling off top layers
// k_eff_b is the largest k' <= B_glob such that H_true(k'-1, D_glob) <= N_glob
long long k_eff_b = 0;
if (B_glob > 0) { // Find k_eff_b
long long low = 1, high = B_glob; // k_eff_b is in [1, B_glob]
k_eff_b = 0; // if N_glob < H_true(0,D_glob) which is N_glob < 0, not possible.
// if N_glob = 0, H_true(0,D_glob)=0, so k_eff_b = 1.
// Max k we might need to check for H_true is ~65.
// If B_glob is very large, k_eff_b will be capped by N_glob.
for (long long k_test = 1; k_test <= B_glob; ++k_test) {
if (get_H_true(k_test - 1, N_glob + 1) <= N_glob) {
k_eff_b = k_test;
} else {
break;
}
// Optimization: if k_test gets too large, H_true will exceed N_glob quickly
if (k_test > 65 && D_glob > 0) { // Heuristic bound, depends on D_glob
if ( (D_glob + 1 > 1 && k_test -1 > 60 ) || (D_glob+1 ==1 && k_test-1 > N_glob+1) ) // (D+1)^k grows fast
break; // No need to iterate B_glob times if B_glob is huge
}
}
if (k_eff_b == 0 && B_glob > 0) k_eff_b = 1; // e.g. N_glob=0
}
long long sum_from_peeled_layers = 0;
if (B_glob > k_eff_b) {
// Sum ( (D_glob+1)^(j+1) - 1 ) for j from k_eff_b to B_glob-1
// This is sum ( (D_glob+1)^p - 1 ) for p from k_eff_b+1 to B_glob
long long first_p = k_eff_b + 1;
long long last_p = B_glob;
if (first_p <= last_p) {
long long num_terms = (last_p - first_p + 1);
long long geom_sum_val;
if (D_glob == 0) { // (D_glob+1) = 1. Sum of 1s.
geom_sum_val = num_terms % MOD;
} else { // D_glob > 0, so D_glob+1 >= 2
long long term_pow_last_p_plus_1 = power(D_glob + 1, last_p + 1);
long long term_pow_first_p = power(D_glob + 1, first_p);
geom_sum_val = (term_pow_last_p_plus_1 - term_pow_first_p + MOD) % MOD;
geom_sum_val = (geom_sum_val * D_inv_glob) % MOD; // D_inv_glob is (D_glob)^{-1}
}
long long minus_one_sum = num_terms % MOD;
sum_from_peeled_layers = (geom_sum_val - minus_one_sum + MOD) % MOD;
}
}
long long ans_recursive_part = actual_calc_recursive(k_eff_b, N_glob);
long long final_ans = (sum_from_peeled_layers + ans_recursive_part) % MOD;
cout << final_ans << endl;
return 0;
}