| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 831007 |
2023-08-19T14:55:18 Z |
rainboy |
Party (INOI20_party) |
C |
|
1391 ms |
428 KB |
#include <stdio.h>
#define MD 1000000007
int min(int a, int b) { return a < b ? a : b; }
int inv(int a) {
return a == 1 ? 1 : (long long) inv(a - MD % a) * (MD / a + 1) % MD;
}
long long count(int d) {
return (1LL << (d + 1) / 2) + (1LL << (d + 2) / 2) - 2;
}
long long power(long long a, long long k) {
long long p = 1;
if (k < 0)
return 0;
while (k) {
if (k & 1)
p = p * a % MD;
a = a * a % MD;
k >>= 1;
}
return p;
}
int main() {
static long long nn[2023];
static int answer[2023];
int q, cnt;
scanf("%d", &q);
cnt = 0;
while (q--) {
long long n, m, k, wl, wm, wr;
int l, y, y_, d, ans;
int h;
scanf("%lld", &n);
h = 0;
while (h < cnt && nn[h] != n)
h++;
if (h < cnt) {
printf("%d\n", answer[h]);
continue;
}
if (n == 1) {
printf("0\n");
continue;
}
l = 0;
while ((1LL << l + 2) - 1 <= n)
l++;
m = n - ((1LL << l + 1) - 1);
ans = 0;
for (y = 0; y <= l + 1; y++)
for (d = 0; d <= y + l + 1; d++) {
k = count(d + min(d, l - y));
if (d > y)
k += (1LL << min(d - y, l) + 1) - 1 - count(d - y + min(d - y, l));
if (y + d > l) {
y_ = (y + l - d + 2) / 2;
wl = m >> l + 1 - y_ << y - y_;
wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
wr = (y <= l ? 1LL << y : m) - wl - wm;
ans = (ans + (power(2, n - (k + (1LL << l + 1 - y_))) - 1)
* (wl % MD)) % MD;
ans = (ans + (power(2, n - (k + (m & (1LL << l + 1 - y_) - 1))) - 1)
* (wm % MD)) % MD;
ans = (ans + (power(2, n - k) - 1)
* (wr % MD)) % MD;
} else
ans = (ans + (power(2, n - k) - 1) * ((1LL << y) % MD)) % MD;
}
ans = (long long) ans * inv((power(2, n) - 1 + MD) % MD) % MD;
if (ans < 0)
ans += MD;
printf("%d\n", ans);
nn[cnt] = n, answer[cnt] = ans, cnt++;
}
return 0;
}
Compilation message
Main.c: In function 'main':
Main.c:54:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
54 | while ((1LL << l + 2) - 1 <= n)
| ~~^~~
Main.c:56:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
56 | m = n - ((1LL << l + 1) - 1);
| ~~^~~
Main.c:62:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
62 | k += (1LL << min(d - y, l) + 1) - 1 - count(d - y + min(d - y, l));
| ~~~~~~~~~~~~~~^~~
Main.c:65:22: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
65 | wl = m >> l + 1 - y_ << y - y_;
| ~~~~~~^~~~
Main.c:65:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
65 | wl = m >> l + 1 - y_ << y - y_;
| ~~^~~~
Main.c:66:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
66 | wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
| ~~^~~~
Main.c:66:55: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
66 | wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
| ~~~~~~^~~~
Main.c:66:61: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
66 | wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
| ~~~~~~~~~~~~~~~~~~~~^~~
Main.c:68:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
68 | ans = (ans + (power(2, n - (k + (1LL << l + 1 - y_))) - 1)
| ~~~~~~^~~~
Main.c:70:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
70 | ans = (ans + (power(2, n - (k + (m & (1LL << l + 1 - y_) - 1))) - 1)
| ~~~~~~^~~~
Main.c:70:63: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
70 | ans = (ans + (power(2, n - (k + (m & (1LL << l + 1 - y_) - 1))) - 1)
| ~~~~~~~~~~~~~~~~~~~~^~~
Main.c:34:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
Main.c:41:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | scanf("%lld", &n);
| ^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
212 KB |
Output is correct |
| 2 |
Correct |
42 ms |
212 KB |
Output is correct |
| 3 |
Correct |
43 ms |
340 KB |
Output is correct |
| 4 |
Correct |
43 ms |
212 KB |
Output is correct |
| 5 |
Correct |
43 ms |
212 KB |
Output is correct |
| 6 |
Correct |
41 ms |
212 KB |
Output is correct |
| 7 |
Correct |
40 ms |
212 KB |
Output is correct |
| 8 |
Correct |
43 ms |
212 KB |
Output is correct |
| 9 |
Correct |
43 ms |
212 KB |
Output is correct |
| 10 |
Correct |
40 ms |
276 KB |
Output is correct |
| 11 |
Correct |
3 ms |
212 KB |
Output is correct |
| 12 |
Correct |
3 ms |
212 KB |
Output is correct |
| 13 |
Correct |
4 ms |
212 KB |
Output is correct |
| 14 |
Correct |
4 ms |
340 KB |
Output is correct |
| 15 |
Correct |
4 ms |
212 KB |
Output is correct |
| 16 |
Correct |
4 ms |
212 KB |
Output is correct |
| 17 |
Correct |
4 ms |
212 KB |
Output is correct |
| 18 |
Correct |
4 ms |
212 KB |
Output is correct |
| 19 |
Correct |
4 ms |
212 KB |
Output is correct |
| 20 |
Correct |
4 ms |
304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
272 KB |
Output is correct |
| 2 |
Correct |
148 ms |
212 KB |
Output is correct |
| 3 |
Correct |
128 ms |
212 KB |
Output is correct |
| 4 |
Correct |
131 ms |
272 KB |
Output is correct |
| 5 |
Correct |
42 ms |
212 KB |
Output is correct |
| 6 |
Correct |
43 ms |
212 KB |
Output is correct |
| 7 |
Correct |
43 ms |
272 KB |
Output is correct |
| 8 |
Correct |
43 ms |
212 KB |
Output is correct |
| 9 |
Correct |
43 ms |
212 KB |
Output is correct |
| 10 |
Correct |
43 ms |
212 KB |
Output is correct |
| 11 |
Correct |
3 ms |
212 KB |
Output is correct |
| 12 |
Correct |
3 ms |
212 KB |
Output is correct |
| 13 |
Correct |
3 ms |
212 KB |
Output is correct |
| 14 |
Correct |
3 ms |
212 KB |
Output is correct |
| 15 |
Correct |
3 ms |
212 KB |
Output is correct |
| 16 |
Correct |
3 ms |
212 KB |
Output is correct |
| 17 |
Correct |
3 ms |
212 KB |
Output is correct |
| 18 |
Correct |
3 ms |
212 KB |
Output is correct |
| 19 |
Correct |
3 ms |
212 KB |
Output is correct |
| 20 |
Correct |
3 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
39 ms |
212 KB |
Output is correct |
| 22 |
Correct |
42 ms |
212 KB |
Output is correct |
| 23 |
Correct |
43 ms |
340 KB |
Output is correct |
| 24 |
Correct |
43 ms |
212 KB |
Output is correct |
| 25 |
Correct |
43 ms |
212 KB |
Output is correct |
| 26 |
Correct |
41 ms |
212 KB |
Output is correct |
| 27 |
Correct |
40 ms |
212 KB |
Output is correct |
| 28 |
Correct |
43 ms |
212 KB |
Output is correct |
| 29 |
Correct |
43 ms |
212 KB |
Output is correct |
| 30 |
Correct |
40 ms |
276 KB |
Output is correct |
| 31 |
Correct |
3 ms |
212 KB |
Output is correct |
| 32 |
Correct |
3 ms |
212 KB |
Output is correct |
| 33 |
Correct |
4 ms |
212 KB |
Output is correct |
| 34 |
Correct |
4 ms |
340 KB |
Output is correct |
| 35 |
Correct |
4 ms |
212 KB |
Output is correct |
| 36 |
Correct |
4 ms |
212 KB |
Output is correct |
| 37 |
Correct |
4 ms |
212 KB |
Output is correct |
| 38 |
Correct |
4 ms |
212 KB |
Output is correct |
| 39 |
Correct |
4 ms |
212 KB |
Output is correct |
| 40 |
Correct |
4 ms |
304 KB |
Output is correct |
| 41 |
Correct |
132 ms |
272 KB |
Output is correct |
| 42 |
Correct |
148 ms |
212 KB |
Output is correct |
| 43 |
Correct |
128 ms |
212 KB |
Output is correct |
| 44 |
Correct |
131 ms |
272 KB |
Output is correct |
| 45 |
Correct |
42 ms |
212 KB |
Output is correct |
| 46 |
Correct |
43 ms |
212 KB |
Output is correct |
| 47 |
Correct |
43 ms |
272 KB |
Output is correct |
| 48 |
Correct |
43 ms |
212 KB |
Output is correct |
| 49 |
Correct |
43 ms |
212 KB |
Output is correct |
| 50 |
Correct |
43 ms |
212 KB |
Output is correct |
| 51 |
Correct |
3 ms |
212 KB |
Output is correct |
| 52 |
Correct |
3 ms |
212 KB |
Output is correct |
| 53 |
Correct |
3 ms |
212 KB |
Output is correct |
| 54 |
Correct |
3 ms |
212 KB |
Output is correct |
| 55 |
Correct |
3 ms |
212 KB |
Output is correct |
| 56 |
Correct |
3 ms |
212 KB |
Output is correct |
| 57 |
Correct |
3 ms |
212 KB |
Output is correct |
| 58 |
Correct |
3 ms |
212 KB |
Output is correct |
| 59 |
Correct |
3 ms |
212 KB |
Output is correct |
| 60 |
Correct |
3 ms |
212 KB |
Output is correct |
| 61 |
Correct |
1 ms |
288 KB |
Output is correct |
| 62 |
Correct |
14 ms |
304 KB |
Output is correct |
| 63 |
Correct |
1351 ms |
324 KB |
Output is correct |
| 64 |
Correct |
1371 ms |
304 KB |
Output is correct |
| 65 |
Correct |
1391 ms |
428 KB |
Output is correct |
| 66 |
Correct |
1371 ms |
328 KB |
Output is correct |
| 67 |
Correct |
44 ms |
308 KB |
Output is correct |
| 68 |
Correct |
43 ms |
296 KB |
Output is correct |
| 69 |
Correct |
43 ms |
300 KB |
Output is correct |
| 70 |
Correct |
43 ms |
312 KB |
Output is correct |
| 71 |
Correct |
43 ms |
312 KB |
Output is correct |
| 72 |
Correct |
43 ms |
316 KB |
Output is correct |
| 73 |
Correct |
4 ms |
388 KB |
Output is correct |
| 74 |
Correct |
4 ms |
340 KB |
Output is correct |
| 75 |
Correct |
4 ms |
340 KB |
Output is correct |
| 76 |
Correct |
4 ms |
340 KB |
Output is correct |
| 77 |
Correct |
4 ms |
340 KB |
Output is correct |
| 78 |
Correct |
4 ms |
340 KB |
Output is correct |
| 79 |
Correct |
4 ms |
340 KB |
Output is correct |
| 80 |
Correct |
4 ms |
300 KB |
Output is correct |
| 81 |
Correct |
3 ms |
340 KB |
Output is correct |
| 82 |
Correct |
4 ms |
340 KB |
Output is correct |
