제출 #635878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635878		S2speed	Party (INOI20_party)	C++17	7 / 100	3046 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;
}

ll tl[130];

void sub2(){
	ll t = -1;
	for(ll i = 0 ; i < 65 ; i++){
		if((1ll << i) == n + 1){
			t = i;
			break;
		}
	}
	if(t == -1) return;
	res = 0;
	for(ll i = 0 , z = 1 ; i < t ; i++ , z <<= 1){
		memset(tl , 0 , sizeof(tl));
		ll v = z , d = i , y = 0 , o = 0;
		if((z << 1) == n + 1){
			y = 1;
			tl[1] = 1;
		}
		tl[t - i - 2] = (1ll << (t - i - 1));
		ll cur = 1 , ps = n;
		for(ll j = 0 ; j < 130 && ps > 0 ; j++){
			ps -= cur;
			ll h = (tav(2 , cur) - 1) * tav(2 , ps) % md * j % md;
			o += h;
			cur -= y;
			y = tl[j];
			cur <<= 1;
			if(v == 1){
				cur--;
				v = 0;
			}
			if(v > 1){
				v >>= 1; d--;
				tl[j + t - d - 1] = (1ll << (t - d - 2));
			}
			cur += (j == 0);
		}
		o %= md;
		o *= z % md; o %= md;
		res += o;
	}
//	cout<<res<<'\n';
	res %= md;
	res *= tav(tav(2 , n) - 1 , md - 2);
	res %= md;
	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