Submission #1003406

#TimeUsernameProblemLanguageResultExecution timeMemory
1003406vjudge1Party (INOI20_party)C++17
7 / 100
3058 ms516 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define endl "\n" using namespace std; using namespace __gnu_pbds; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; const ll mod = 1e9 + 7; ll n; ll freq[20]; ll binpow(ll n, ll p) { ll ans = 1; while (p) { ans = (p & 1 ? (ans * n) % mod : ans); n = (n * n) % mod; p >>= 1; } return ans; } ll inv(ll x) { return binpow(x, mod - 2); } void dfs(ll v, ll par = 0, ll depth = 0) { freq[depth]++; for (ll to : {v >> 1, v * 2, v * 2 + 1}) if (to != par and to <= n and to >= 1) dfs(to, v, depth + 1); } void solve() { cin >> n; ll ans = 0; for (ll i = 1; i <= n; i++) { for (ll j = 0; j < 20; j++) freq[j] = 0; dfs(i); ll cur = 0; for (ll j = 19; j >= 0; j--) ans = (ans + binpow(2, cur) * (binpow(2, freq[j]) - 1) % mod * j % mod) % mod, cur += freq[j]; } ans = ans * inv(binpow(2, n) - 1 + mod) % mod;; cout << ans << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll t = 1; // precomp(); cin >> t; for (ll cs = 1; cs <= t; cs++) solve(); // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...