// 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 = 62;
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 < 61; 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;
for (int j = 1; j < v.size(); ++j) {
c += v[j];
dp[i] = (dp[i] + (bp(2, v[j]) - 1) * bp(2, n - c) % mod * j % mod * mk) % mod;
}
ans = (ans + dp[i] * ((1ll << i) % mod)) % mod;
}
cout << ans << '\n';
}
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) {
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
