# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
633679 |
2022-08-23T03:47:56 Z |
406 |
Party (INOI20_party) |
C++17 |
|
3000 ms |
780 KB |
#include <bits/stdc++.h>
using ll = unsigned long long;
using namespace std;
#define forn(a, b) for (int a = 0; a < (b); a++)
#define rofn(a, b) for (int a = (b) - 1; a >= 0; a--)
#define LOG(a) (63 - __builtin_clzll(a))
#define chmx(a, b) a = max(a, b)
#define chmn(a, b) a = min(a, b)
#define pb push_back
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1,*p2;
inline int read() {
int x = 0, f = 1; char c;
while(!isdigit(c = gc())) if(c=='-') f=-1;
while(isdigit(c)) x = (x<<3)+(x<<1)+(c^48), c = gc();
return x * f;
}
#define int ll
const ll INFL = 1ll << 60;
const int INF = 1 << 29;
const int N = 256;
const int MOD = 1e9 + 7;
ll d[2][N][N], ptr, q, ans, n;
ll pw(ll a, ll b) {
assert(b >= 0);
b %= (MOD - 1);
a %= MOD;
ll re = 1;
while (b) {
if (b & 1)
re = (re * a) % MOD;
a = (a * a) % MOD;
b /= 2;
}
return re;
}
void calc_dist(ll v, ll sub, int lg) {
for (int k = lg; k < N; k++) {
int x = k - lg;
if ((x + lg) > 62 || (v << x) > n)
break;
d[1][ptr][x] = min(n - (v << x) + 1, ((ll)1 << x));
}
if (v > 1) {
for (int k = 2; k < N; k++)
d[0][ptr][k] -= d[1][ptr][k - 2];
}
}
void pass() {
for (int k = 1; k < N; k++)
d[0][ptr + 1][k] = d[0][ptr][k - 1] + d[1][ptr][k - 1];
ptr++;
assert(ptr <= N);
}
void clear() {
for (int b = 0; b < 2; b++)
for (int i = 0; i < N; i++)
d[b][ptr][i] = 0;
ptr--;
}
void Complete(ll v, ll sub, int lg) {
if (v > n) {
clear();
return;
}
//cout << "C: " << v << ' ' << sub << " PTR: " << ptr << '\n';
calc_dist(v, sub, lg);
pass();
Complete(v * 2, sub / 2, lg + 1);
q += q;
q %= MOD;
ll s = 0;
for (int k = 0; k < N; k++) {
if (!d[0][ptr][k] && !d[1][ptr][k])
continue;
s += d[0][ptr][k] + d[1][ptr][k];
ll t = pw(2, d[0][ptr][k] + d[1][ptr][k]) - 1;
t %= MOD;
q += (k * t % MOD) * pw(2, n - s) % MOD;
q %= MOD;
}
clear();
}
void F(ll v, ll sub, int lg) {
if (v > n) {
clear();
return;
}
//cout << "F: " << v << ' ' << sub << " PTR: " << ptr << '\n';
calc_dist(v, sub, lg);
ll r = v * 2 + 1;
ll l = v * 2;
int cntr = 0, cntl = 0;
while (r <= n)
r *= 2ll, cntr++;
while (l <= n)
l *= 2ll, cntl++;
if (cntr == cntl) {
q = 0;
pass();
Complete(v * 2, (1ll << cntl) - 1, lg + 1);
ans += q;
ans %= MOD;
pass();
F(v * 2 + 1, sub - (1ll << cntl), lg + 1);
}
else {
q = 0;
pass();
Complete(v * 2 + 1, (1ll << cntr) - 1,lg + 1);
ans += q;
ans %= MOD;
pass();
F(v * 2, sub - (1ll << cntr), lg + 1);
}
ll s = 0;
for (int k = 0; k < N; k++) {
if (!d[0][ptr][k] && !d[1][ptr][k])
continue;
s += d[0][ptr][k] + d[1][ptr][k];
ll t = pw(2, d[0][ptr][k] + d[1][ptr][k]) - 1;
t %= MOD;
ans += k * t % MOD * pw(2, n - s) % MOD;
ans %= MOD;
assert(s <= n);
}
assert(ans >= 0 && ans <= MOD);
clear();
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
int query;
cin >> query;
while (query--) {
cin >> n;
F(1, n, 1);
ll re = pw(2, n) - 1;
re %= MOD;
ans = (ans * pw(re, MOD - 2)) % MOD;
cout << ans << '\n';
ans = q = ptr = 0;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
6 ms |
468 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
340 KB |
Output is correct |
5 |
Correct |
4 ms |
340 KB |
Output is correct |
6 |
Correct |
4 ms |
340 KB |
Output is correct |
7 |
Correct |
4 ms |
340 KB |
Output is correct |
8 |
Correct |
4 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
340 KB |
Output is correct |
10 |
Correct |
4 ms |
324 KB |
Output is correct |
11 |
Correct |
77 ms |
376 KB |
Output is correct |
12 |
Correct |
80 ms |
376 KB |
Output is correct |
13 |
Correct |
91 ms |
364 KB |
Output is correct |
14 |
Correct |
76 ms |
372 KB |
Output is correct |
15 |
Correct |
72 ms |
372 KB |
Output is correct |
16 |
Correct |
71 ms |
384 KB |
Output is correct |
17 |
Correct |
75 ms |
368 KB |
Output is correct |
18 |
Correct |
71 ms |
376 KB |
Output is correct |
19 |
Correct |
75 ms |
332 KB |
Output is correct |
20 |
Correct |
87 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1965 ms |
560 KB |
Output is correct |
2 |
Correct |
2292 ms |
676 KB |
Output is correct |
3 |
Correct |
2001 ms |
556 KB |
Output is correct |
4 |
Correct |
1762 ms |
476 KB |
Output is correct |
5 |
Correct |
2099 ms |
564 KB |
Output is correct |
6 |
Correct |
2031 ms |
552 KB |
Output is correct |
7 |
Correct |
1855 ms |
556 KB |
Output is correct |
8 |
Correct |
1952 ms |
556 KB |
Output is correct |
9 |
Correct |
1909 ms |
588 KB |
Output is correct |
10 |
Correct |
2025 ms |
556 KB |
Output is correct |
11 |
Execution timed out |
3087 ms |
596 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1870 ms |
548 KB |
Output is correct |
2 |
Correct |
2096 ms |
560 KB |
Output is correct |
3 |
Correct |
1808 ms |
564 KB |
Output is correct |
4 |
Correct |
1859 ms |
552 KB |
Output is correct |
5 |
Correct |
2083 ms |
560 KB |
Output is correct |
6 |
Correct |
2080 ms |
588 KB |
Output is correct |
7 |
Correct |
1997 ms |
560 KB |
Output is correct |
8 |
Correct |
2128 ms |
560 KB |
Output is correct |
9 |
Correct |
1941 ms |
556 KB |
Output is correct |
10 |
Correct |
2111 ms |
780 KB |
Output is correct |
11 |
Execution timed out |
3092 ms |
468 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
6 ms |
468 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
340 KB |
Output is correct |
5 |
Correct |
4 ms |
340 KB |
Output is correct |
6 |
Correct |
4 ms |
340 KB |
Output is correct |
7 |
Correct |
4 ms |
340 KB |
Output is correct |
8 |
Correct |
4 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
340 KB |
Output is correct |
10 |
Correct |
4 ms |
324 KB |
Output is correct |
11 |
Correct |
77 ms |
376 KB |
Output is correct |
12 |
Correct |
80 ms |
376 KB |
Output is correct |
13 |
Correct |
91 ms |
364 KB |
Output is correct |
14 |
Correct |
76 ms |
372 KB |
Output is correct |
15 |
Correct |
72 ms |
372 KB |
Output is correct |
16 |
Correct |
71 ms |
384 KB |
Output is correct |
17 |
Correct |
75 ms |
368 KB |
Output is correct |
18 |
Correct |
71 ms |
376 KB |
Output is correct |
19 |
Correct |
75 ms |
332 KB |
Output is correct |
20 |
Correct |
87 ms |
376 KB |
Output is correct |
21 |
Correct |
1965 ms |
560 KB |
Output is correct |
22 |
Correct |
2292 ms |
676 KB |
Output is correct |
23 |
Correct |
2001 ms |
556 KB |
Output is correct |
24 |
Correct |
1762 ms |
476 KB |
Output is correct |
25 |
Correct |
2099 ms |
564 KB |
Output is correct |
26 |
Correct |
2031 ms |
552 KB |
Output is correct |
27 |
Correct |
1855 ms |
556 KB |
Output is correct |
28 |
Correct |
1952 ms |
556 KB |
Output is correct |
29 |
Correct |
1909 ms |
588 KB |
Output is correct |
30 |
Correct |
2025 ms |
556 KB |
Output is correct |
31 |
Execution timed out |
3087 ms |
596 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |