Submission #1037841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037841		javotaz	Party (INOI20_party)	C++17	0 / 100	1 ms	464 KiB

Main

// In the Name of Allah

#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,avx,avx2,sse4.2,popcnt,tune=native")

typedef long long ll;

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

const int N = 61;

const int mod = 1'000'000'000 + 7;
ll n, dp[N];

int bp(int x, ll y) {
	if (y < 2) return y? x : 1;
	ll tmp = bp(x, y / 2);
	tmp = tmp * tmp % mod;
	return (y & 1)? tmp * x % mod : tmp;
}

void solve() {
	cin >> n;
	ll ans = 0;
	int k = __lg(n) + 1;
	if (n != (1ll << k) - 1)
		return;
	ll mk = bp(bp(2, n) - 1, mod - 2);
	for (int i = 0; i < k; i++) {
		vector<ll> v;
		v.pb(1);
		for (int j = 1; j < 2 * k; ++j) {
			ll cnt = (i + j < k)? (1ll << j) : 0;
			for (int z = i - 1; z >= 0; z--)
				if (j == (i - z))
					cnt++;
				else if (j > (i - z) && z + j - (i - z) < k)
					cnt += (1ll << (j - (i - z) - 1));
			if (!cnt)
				break;
			v.pb(cnt);
		}
		ll c = 0;
		for (auto i: v) {
			c += i;
			dp[i] = (dp[i] + (bp(2, i) - 1) * bp(2, n - i) % mod * mk) % mod;
		}
		ans = (ans + dp[i] * ((1ll << i) % mod)) % mod;
	}
	cout << ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}

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