Submission #635856

#	Time	Username	Problem	Language	Result	Execution time	Memory
635856		S2speed	Party (INOI20_party)	C++17	7 / 100	7 ms	340 KiB

Main

#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 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 33
• Subtask 4: 0 / 37