Submission #782859

#	Time	Username	Problem	Language	Result	Execution time	Memory
782859		MISM06	Party (INOI20_party)	C++14	0 / 100	77 ms	508 KiB

Main

//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kids		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;


const ll N = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll INF = 1e9 + 10;
const ll lg = 32;

inline void add (ll &x, ll y) {
	x += y; if (x >= mod) x-= mod;
	if (x < 0) x += mod;
}
inline ll Sum (ll x, ll y) {
	x += y; if (x >= mod) x -= mod;
	if (x < 0) x += mod;
	return x;
}
inline ll mul (ll x, ll y) {
	return (((x * y) % mod) + mod) % mod;
}
inline ll pw (ll x, ll y) {
	x %= mod;
	ll res = 1;
	while (y) {
		if (y & 1) res = mul(x, res);
		x = mul(x, x);
		y >>= 1;
	}
	return res;
}

ll dp[100][200], pd[100][200], p[62];

void solve () {

	ll n;
	cin >> n;
	ll h = 0;
	p[0] = 1;
	for (ll i = 1; i < 62; i++) {
		p[i] = p[i - 1] * 2ll;
	}
	while(p[h] < n) {
		++h;
	}
	--h;
	for (ll i = 0; i <= h; i++) {
		for (ll j = 0; j <= h - i; j++) {
			dp[i][j] = p[h - i + 1] - p[j]; 
		}
	}
	for (ll i = 0; i <= h; i++) {
		for (int j = 0; j <= h; j++) {
			if (i == 0) pd[i][j] = dp[i][j];
			else {
				pd[i][j] = dp[i][j];
				pd[i][j] += pd[i - 1][max(0, j - 1)];
				pd[i][j] -=dp[i][max(0, j - 2)];
			}
		}
	}
	// cout << "h = " << h << '\n';
	// for (int i = 0; i <= h; i++) {
	// 	for (int j = 0; j <= h; j++) cout << i << " , " << j << " : " << dp[i][j] << " - " << pd[i][j] << '\n';
	// }
	ll ans = 0;
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= h; j++) add(ans, mul(p[i], Sum(pw(2, pd[i][j]), -1)));
	}
	ans = mul(ans, pw(pw(2, n) - 1, mod - 2));
	cout << ans << '\n';

}


int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) {solve();}
    return 0;
}
/*
*/
//shrek is love;

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