oj.uz

Submission #1037888

# Submission time Handle Problem Language Result Execution time Memory
1037888 2024-07-29T09:47:45 Z javotaz Party (INOI20_party) C++17
0 / 100
 50 ms 348 KB 
// 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 = 64;

const int mod = 1'000'000'000 + 7;
int ans[N];

ll 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;
}

int solve(ll n) {
	ll ans = 0;
	int k = 0;
	for (int i = 0; i < 62; i++)
		if ((1ll << i) - 1 == n)
			k = i;
	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 = 1, res = 0;
		for (int j = 1; j < v.size(); ++j) {
			c += v[j];
			res = (res + (bp(2, v[j]) - 1) * bp(2, n - c) % mod * j % mod * mk) % mod;
		}
		ans = (ans + res * ((1ll << i) % mod)) % mod;
	}
	return ans;
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	for (int i = 0; i < 62; i++)
		ans[i] = solve((1ll << i) - 1);
	int t;
	cin >> t;
	while (t--) {
		int x;
		cin >> x;
		cout << ans[__lg(x) + 1] << '\n';
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int solve(ll)':
Main.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int j = 1; j < v.size(); ++j) {
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -