oj.uz

Submission #1037885

# Submission time Handle Problem Language Result Execution time Memory
1037885 2024-07-29T09:42:10 Z javotaz Party (INOI20_party) C++17
0 / 100
 3000 ms 460 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()
#define int long long

const int N = 64;

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 = 0;
	for (int i = 0; i < 62; i++)
		if ((1ll << i) - 1 == n)
			k = i;
	if (n != (1ll << k) - 1)
		exit(0);
	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;
	}
	cout << ans << endl;
	memset(dp, 0, sizeof dp);
}

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

Compilation message

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 Correct 142 ms 348 KB Output is correct
2 Correct 164 ms 348 KB Output is correct
3 Correct 150 ms 348 KB Output is correct
4 Correct 129 ms 348 KB Output is correct
5 Correct 158 ms 348 KB Output is correct
6 Correct 149 ms 344 KB Output is correct
7 Correct 137 ms 348 KB Output is correct
8 Correct 139 ms 348 KB Output is correct
9 Correct 137 ms 348 KB Output is correct
10 Correct 153 ms 348 KB Output is correct
11 Execution timed out 3098 ms 460 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

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

Subtask #4
0 / 37.0

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