# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1005383 | aykhn | Party (INOI20_party) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
const int MXN = 3e5 + 5;
const int LOG = 60;
const int mod = 1e9 + 7;
int add(int a, int b)
{
return (a + b + mod) % mod;
}
int mult(int a, int b)
{
return (a * b) % mod;
}
int p1[10001], p2[100001];
int d[LOG * 2];
int pw(int x)
{
return mult(p2[(x % (mod - 1)) / 10000], p1[(x % (mod - 1)) % 10000]);
}
int pw(int a, int b, int c)
{
a %= c;
int res = 1;
while (b)
{
if (b & 1) res = (res * a) % c;
a = (a * a) % c;
b >>= 1;
}
return res;
}
int n, res = 0, sz, lay;
void dfs(int a, int l, int r)
{
int s = 0;
for (int i = LOG * 2 - 1; i >= 1; i--)
{
s = add(s, d[i]);
res = add(res, add(pw(s), -1));
}
if (lay >= l + ((r - l + 1) / 2))
{
res = add(res, calcsub(2 * i));
}
else
{
res = (add, res, calcsub(2 * i + 1));
}
}
void _()
{
cin >> n;
for (int i = 0; i < LOG * 2; i++)
{
d[i] = max(0LL, min(add(n, -add(pw(i), -1)), pw(i)));
if (d[i]) lay = d[i], sz = (1LL << i);
}
dfs(1, 1, sz);
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
p1[0] = 1, p2[0] = 1;
for (int i = 1; i <= 10000; i++) p1[i] = (p1[i - 1] << 1) % mod;
for (int i = 1; i <= 100000; i++) p2[i] = (p2[i - 1] * p1[10000]) % mod;
int t;
cin >> t;
while (t--)
{
_();
}
}