結果
問題 | 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 > posint 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;}