| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 782881 |
2023-07-14T10:48:01 Z |
MISM06 |
Party (INOI20_party) |
C++17 |
|
111 ms |
496 KB |
//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)];
}
}
for (int j = h + 1; j <= h + h; ++j) {
int x = j - i - 1;
if (x >= h) continue;
pd[i][j] = dp[1][x];
}
}
// cout << "h = " << h << '\n';
// for (int i = 0; i <= h; i++) {
// for (int j = 0; j <= h + 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 = 1; j <= h + 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';
for (int i = 0; i <= h + 1; i++) {
for (int j = 0; j <= h + h + 2; j++) dp[i][j] = pd[i][j] = 0;
}
}
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;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
111 ms |
496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
108 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
