Submission #760206

#TimeUsernameProblemLanguageResultExecution timeMemory
760206The_SamuraiParty (INOI20_party)C++17
0 / 100
3071 ms212 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; const ll mod = 1e9 + 7; ll binpow(ll a, ll b, ll mod, bool dec = false) { ll ans = 1; while (b) { if (b & 1) { ans = ans * a % mod; } a = a * a % mod; b >>= 1; } if (dec) { ans = (ans - 1 + mod) % mod; } return ans; } bool isTwo(ll n) { return (1ll << (63 - __builtin_clzll(n))) == n; } ll n, ans; ll cnt(ll x, ll h) { // x dan h ta pastda turgan nechta bor? if ((x << h) > n) { return 0; } return min(n, (x << h) + (1 << h) - 1) - (x << h) + 1; } void calc(ll x, ll mul) { vector<tuple<ll, ll, bool>> g = {{x, 0, true}}; ll others = n, sum_all = 0; for (int h = 0; h <= n; h++) { vector<tuple<ll, ll, bool>> nw; ll sum = 0; for (auto [v, t, change]: g) { sum += cnt(v, t); if (!change) { if (v * 2 <= n) { nw.emplace_back(v, t + 1, change); } continue; } if (x == v) { if (v * 2 <= n) { nw.emplace_back(v, t + 1, false); } if (v > 1) { nw.emplace_back(v / 2, 0, true); } continue; } if (isTwo(x / v) and x % v == 0) { if (v * 2 + 1 <= n) { nw.emplace_back(v * 2 + 1, 0, false); } if (v > 1) { nw.emplace_back(v / 2, 0, true); } continue; } } others -= sum; // cout << h << ' ' << sum << ' ' << others << endl; ll k = binpow(2, sum, mod, true) * binpow(2, others, mod) % mod; sum_all = (sum_all + k * h) % mod; if (nw.empty()) { break; } g = nw; } mul %= mod; ans = (ans + sum_all * mul) % mod; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int q; cin >> q; map<ll, int> mp; for (int qq = 1; qq <= q; qq++) { cin >> n; // n = (1ll << 59) - 1; if (mp.count(n)) { cout << mp[n] << '\n'; continue; } ans = 0; for (ll x = 1; x < n; x *= 2) { calc(x, x); } ans = ans * binpow(binpow(2, n, mod, true), mod - 2, mod) % mod; cout << ans << '\n'; mp[n] = ans; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...