oj.uz

Submission #466179

# Submission time Handle Problem Language Result Execution time Memory
466179 2021-08-18T10:25:41 Z sinamhdv Party (INOI20_party) C++11
7 / 100
 598 ms 660 KB 
#include <bits/stdc++.h>
using namespace std;

#define int ll

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define endl '\n'

const int MAXN = 220;
const int MAXH = 22;

int q;
ll n;
int k;
int dp[MAXN][MAXH];
ll ans;
int h[MAXN];
int rt;
vector<int> adj[MAXN];

inline void addedge(int x, int y)
{
	adj[x].pb(y);
	adj[y].pb(x);
}

void dfs(int v, int par)
{
	dp[rt][h[v]]++;
	for (int u : adj[v]) if (u != par) h[u] = h[v] + 1, dfs(u, v);
}

ll poww(ll a, ll b)
{
	a %= mod, b %= mod;
	ll res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b /= 2;
	}
	return res;
}

inline void tcase(void)
{

	ans = 0;
	FOR(i, 0, MAXN) adj[i].clear();
	memset(dp, 0, sizeof(dp));

	cin >> n;

	FOR(i, 2, n + 1)
	{
		addedge(i, i/2);
	}

	FOR(i, 1, n + 1)
	{
		rt = i;
		h[i] = 0;
		dfs(i, -1);
		for (int x = MAXH - 2; x >= 0; x--) dp[i][x] += dp[i][x + 1];
		ll val = 0;
		FOR(x, 1, MAXH - 1) val += (ll)x * (poww(2, dp[i][x]) - poww(2, dp[i][x + 1])) % mod;
		ans = (ans + val) % mod;
	}

	ans = ans * poww((poww(2, n) - 1) % mod, mod - 2) % mod;
	ans = (mod + ans % mod) % mod;
	cout << ans << endl;
}

int32_t main(void)
{
	fast_io;

	cin >> q;
	while (q--) tcase();

	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 10 ms 332 KB Output is correct
3 Correct 10 ms 356 KB Output is correct
4 Correct 9 ms 356 KB Output is correct
5 Correct 14 ms 360 KB Output is correct
6 Correct 11 ms 364 KB Output is correct
7 Correct 13 ms 356 KB Output is correct
8 Correct 15 ms 356 KB Output is correct
9 Correct 13 ms 356 KB Output is correct
10 Correct 15 ms 332 KB Output is correct
11 Correct 598 ms 364 KB Output is correct
12 Correct 596 ms 364 KB Output is correct
13 Correct 584 ms 364 KB Output is correct
14 Correct 585 ms 456 KB Output is correct
15 Correct 579 ms 364 KB Output is correct
16 Correct 590 ms 496 KB Output is correct
17 Correct 354 ms 364 KB Output is correct
18 Correct 350 ms 348 KB Output is correct
19 Correct 358 ms 364 KB Output is correct
20 Correct 353 ms 360 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 660 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 10 ms 332 KB Output is correct
3 Correct 10 ms 356 KB Output is correct
4 Correct 9 ms 356 KB Output is correct
5 Correct 14 ms 360 KB Output is correct
6 Correct 11 ms 364 KB Output is correct
7 Correct 13 ms 356 KB Output is correct
8 Correct 15 ms 356 KB Output is correct
9 Correct 13 ms 356 KB Output is correct
10 Correct 15 ms 332 KB Output is correct
11 Correct 598 ms 364 KB Output is correct
12 Correct 596 ms 364 KB Output is correct
13 Correct 584 ms 364 KB Output is correct
14 Correct 585 ms 456 KB Output is correct
15 Correct 579 ms 364 KB Output is correct
16 Correct 590 ms 496 KB Output is correct
17 Correct 354 ms 364 KB Output is correct
18 Correct 350 ms 348 KB Output is correct
19 Correct 358 ms 364 KB Output is correct
20 Correct 353 ms 360 KB Output is correct
21 Runtime error 1 ms 588 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -