Submission #469028

#	Time	Username	Problem	Language	Result	Execution time	Memory
469028		Millad	Party (INOI20_party)	C++14	7 / 100	495 ms	412 KiB

Main

// In the name of god
#include <bits/stdc++.h>
     
#define F first
#define S second
#define pb push_back
#define debug(x) cerr << #x << " : " << x << '\n'
     
using namespace std;
 typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
     
const ll maxn = 205;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

ll ans[maxn], PW[maxn], PW2[maxn], dis[maxn], pw2[maxn], cnt[maxn];
vector <ll> adj[maxn];
ll pw(ll A, ll B){
	ll RES = 1;
	while(B){
		if(B % 2ll)RES = (RES * A) % mod;
		B /= 2ll; A = (A * A) % mod;
	}
	return RES;
}
bool mrk[maxn];
void find_dis(ll v, ll n){
	for(ll i = 1; i <= n; i ++){
		dis[i] = inf;
		cnt[i] = 0; mrk[i] = 0;
	}
	dis[v] = 0; cnt[0] = 0;
	queue<ll> q; q.push(v);
	while(q.size()){
		ll u = q.front(); q.pop();
		if(mrk[u])continue;
		mrk[u] = 1; cnt[dis[u]] ++;
		for(ll j : adj[u]){
			if(dis[j] > dis[u] + 1ll){
				dis[j] = dis[u] + 1ll;
				q.push(j);
			}
		}
	}
}
ll solve(ll n){
       	for(ll i = 1; i <= n; i ++)adj[i].clear();
	for(ll i = 1; i <= n; i ++){
		if(i / 2ll)adj[i].pb(i / 2ll);
		if(i + i <= n)adj[i].pb(i + i);
		if(i + i + 1 <= n)adj[i].pb(i + i + 1);
	}
	ll sum = 0;
	for(ll i = 1; i <= n; i ++){
		find_dis(i, n);
		ll CNT = 0;
		for(ll j = 0; j < n; j ++){
			sum = (sum + (((pw2[n - CNT] - 1ll + mod) % mod) - ((pw2[n - CNT - cnt[j]] - 1ll + mod) % mod) + mod) * pw((pw2[n] - 1ll + mod) % mod, mod - 2) % mod * j % mod) % mod;
			CNT += cnt[j];
		}
	}
	return sum;
}	
int main(){
	pw2[0] = 1;
	for(ll i = 1; i < maxn; i ++)pw2[i] = (pw2[i - 1] * 2ll) % mod;
	for(ll i = 2; i < 201; i ++)ans[i] = solve(i);
	ll q; cin >> q;
	while(q --){
		ll n; cin >> n;
		cout << ans[n] << endl;
	}
}

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