結果
問題 |
No.681 Fractal Gravity Glue
|
ユーザー |
![]() |
提出日時 | 2018-04-28 00:13:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,390 bytes |
コンパイル時間 | 2,352 ms |
コンパイル使用メモリ | 193,056 KB |
最終ジャッジ日時 | 2025-01-05 10:27:02 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> using namespace std; using int64 = long long; const int mod = 1e9 + 7; int64 N, B, D; int64 Dinv; int64 f(int idx) { int64 base = 1; for(int i = 0; i < idx; i++) { base *= D + 1; if(base > mod) break; } return min(base - 1, 1LL << 30); } int64 mod_pow(int64 x, int64 n, int64 mod) { int64 ret = 1; while(n > 0) { if(n & 1) (ret *= x) %= mod; (x *= x) %= mod; n >>= 1; } return ret; } // あー人生ね あー int64 g(int idx) { int64 base = mod_pow(D + 1, idx + 1, mod); (base = mod - base) %= mod; base += D * idx % mod; base %= mod; base += D; base %= mod; base += 1; base %= mod; base *= Dinv; base %= mod; (base = mod - base) %= mod; return base; } int64 dfs(int idx, int pos) { if(pos == 0) return 0; if(idx == 1) return pos; int64 basesz = f(idx - 1) + 1; int64 sz = pos / basesz; if(sz == 0) { // basesz > pos int ok = 1, ng = idx; while(ng - ok > 1) { int mid = (ok + ng) / 2; if(f(mid - 1) + 1 /* basesz*/ <= pos) ok = mid; else ng = mid; } return dfs(ok, pos); } int64 ret = 1LL * sz * idx % mod; ret += g(idx - 1) * sz % mod; ret %= mod; ret += dfs(idx - 1, pos - sz * basesz) % mod; return ret % mod; } int main() { cin >> N >> B >> D; Dinv = mod_pow(D, mod - 2, mod); cout << (g(B) + mod - dfs(B, N)) % mod << endl; }