Submission #760184

#TimeUsernameProblemLanguageResultExecution timeMemory
760184drdilyorParty (INOI20_party)C++17
0 / 100
3071 ms354260 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; #define DEBUG #if defined(ONPC) && !defined(NODEBUG) #define debug(args...) cout << "["<< #args << "]= "; debug_out(args); #else #define debug(args...) 42; #endif void debug_out() { cout << endl; } template<typename H, typename... T> void debug_out(H h, T... t) { cout << h; if (sizeof...(t)) cout << ", "; debug_out(t...); } constexpr int mod = 1e9 + 7; ll modpow(ll a, ll b) { a %= mod; ll res = 1; while (b) { if (b&1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } ll inv(ll x) { return modpow(x, mod-2); } ll pw2(ll x) { return x < 0 ? 0 :(1LL << x); } ll sub(ll a, ll b) { a -= b; return a < 0 ? a + mod : a; } ll solve(ll n) { auto comb = [&](int chosen)->ll{ return sub(modpow(2, n - chosen), 1); }; vector<vector<int>> adj(n); for (int i = 0; i < n; i++) { int p = (i+1) / 2-1; if (p>=0) { adj[p].push_back(i); adj[i].push_back(p); } } int cover=0, perim=0; auto dfs = [&](auto& dfs, int i, int p, int dist)->void { if (dist == 0) { perim++; return; } else cover++; for (int e : adj[i]) { if (e!=p) dfs(dfs, e, i, dist-1); } }; ll res = 0; for (int i = 0; i < n; i = i *2+1) { for (int d = 1; ; d++) { cover = perim = 0; dfs(dfs, i, -1, d); if (perim == 0) break; int ni = min((int)n, i* 2+1); int cnt = ni - i; debug(i, cover, perim, cnt); res += cnt * d % mod * sub(comb(cover), comb(cover + perim)) % mod; } } debug(res, comb(0)); return res * inv(comb(0)) % mod; } int main() { cin.tie(0)->sync_with_stdio(0); int q; cin >> q; while (q--) { ll n; cin >> n; cout << solve(n) << '\n'; } }

Compilation message (stderr)

Main.cpp: In function 'll solve(ll)':
Main.cpp:8:24: warning: statement has no effect [-Wunused-value]
    8 | #define debug(args...) 42;
      |                        ^~
Main.cpp:72:13: note: in expansion of macro 'debug'
   72 |             debug(i, cover, perim, cnt);
      |             ^~~~~
Main.cpp:8:24: warning: statement has no effect [-Wunused-value]
    8 | #define debug(args...) 42;
      |                        ^~
Main.cpp:76:5: note: in expansion of macro 'debug'
   76 |     debug(res, comb(0));
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...