Submission #760071

#TimeUsernameProblemLanguageResultExecution timeMemory
760071The_SamuraiParty (INOI20_party)C++17
0 / 100
3068 ms212 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; const ll mod = 1e9 + 7; ll binpow(ll a, int 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 (1 << (63 - __builtin_clzll(n))) == n; } ll n, ans; int calc(ll x, ll mul) { vector<pair<ll, int>> g = {{x, 1}}; ll others = n; for (int h = 0; h <= n; h++) { vector<pair<ll, int>> nw; ll sum = 0; for (auto [v, t]: g) { sum += t; if (x == v) { if (v * 2 <= n) { nw.emplace_back(v * 2, t * 2); } if (v > 1) { nw.emplace_back(v / 2, 1); } continue; } if (isTwo(x / v) and x % v == 0) { // parent if (v * 2 + 1 <= n) { nw.emplace_back(v * 2 + 1, 1); } if (v != 1) { nw.emplace_back(v / 2, 1); } continue; } if (v * 2 <= n) { nw.emplace_back(v * 2, t * 2); } } others -= sum; ll k = binpow(2, sum % mod, mod, true) * binpow(2, others % mod, mod) % mod; // cout << x << ' ' << h << ' ' << sum << ' ' << k * mul << endl; ans = (ans + k * h % mod * mul) % mod; if (nw.empty()) { break; } g = nw; } } int main() { int q; cin >> q; while (q--) { cin >> n; ans = 0; for (ll x = 1; x < n; x *= 2) { calc(x, x); } cout << ans * binpow(binpow(2, n, mod, true), mod - 2, mod) % mod << '\n'; } } // 1 - 1 2 4 8 // 2 - 1 3 8 2 4 // 4 - 1 3 2 3 2 4

Compilation message (stderr)

Main.cpp: In function 'int calc(ll, ll)':
Main.cpp:69:1: warning: no return statement in function returning non-void [-Wreturn-type]
   69 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...