Submission #760184

#	Time	Username	Problem	Language	Result	Execution time	Memory
760184		drdilyor	Party (INOI20_party)	C++17	0 / 100	3071 ms	354260 KiB

Main

#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));
      |     ^~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 33
• Subtask 4: 0 / 37