oj.uz

Submission #635856

# Submission time Handle Problem Language Result Execution time Memory
635856 2022-08-27T08:11:40 Z S2speed Party (INOI20_party) C++17
7 / 100
 7 ms 340 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;

const ll maxn = 206 , md = 1e9 + 7 , inf = 2e16;

inline ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

ll n , ans[maxn];
vector<ll> adj[maxn] , bfs;
ll dis[maxn] , cnt[maxn] , res;

void BFS(ll r){
	memset(dis , 63 , sizeof(dis));
	bfs.clear();
	dis[r] = 0;
	bfs.push_back(r);
	ll x = 0;
	while(x < sze(bfs)){
		ll v = bfs[x++];
		for(auto i : adj[v]){
			if(dis[i] < inf) continue;
			dis[i] = dis[v] + 1;
			bfs.push_back(i);
		}
	}
	return;
}

void sub1(){
	if(ans[n] != -1){
		cout<<ans[n]<<'\n';
		return;
	}
	res = 0;
	for(ll i = 0 ; i < n ; i++) adj[i].clear();
	for(ll i = 1 ; i < n ; i++){
		ll par = (i - 1) >> 1;
		adj[par].push_back(i); adj[i].push_back(par);
	}
	for(ll i = 0 ; i < n ; i++){
		BFS(i);
		memset(cnt , 0 , sizeof(cnt));
		for(ll j = 0 ; j < n ; j++){
			cnt[dis[j]]++;
		}
		ll ps = n;
		for(ll d = 0 ; d < n ; d++){
			if(cnt[d] == 0) break;
			ps -= cnt[d];
			ll h = (tav(2 , cnt[d]) - 1) * tav(2 , ps) % md * d % md;
			res += h;
		}
	}
//	cout<<res<<'\n';
	res %= md;
	res *= tav(tav(2 , n) - 1 , md - 2);
	res %= md;
	ans[n] = res;
	cout<<res<<'\n';
	return;
}

void solve(){
	cin>>n;
	if(n <= 200){
		sub1();
		return;
	}
//	sub2();
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(ans , -1 , sizeof(ans));
	ll T;
	cin>>T;
	while(T--) solve();
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 7 ms 336 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 5 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 7 ms 336 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 5 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -