| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 831003 |
2023-08-19T14:51:03 Z |
rainboy |
Party (INOI20_party) |
C |
|
3000 ms |
304 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() {
int q;
scanf("%d", &q);
while (q--) {
long long n, m, k, wl, wm, wr;
int l, y, y_, d, ans;
scanf("%lld", &n);
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 (m == 0 && 0) {
if (y <= l)
ans = (ans + (power(2, n - k) - 1) * ((1LL << y) % MD)) % MD;
} else {
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);
}
return 0;
}
Compilation message
Main.c: In function 'main':
Main.c:43:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
43 | while ((1LL << l + 2) - 1 <= n)
| ~~^~~
Main.c:45:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
45 | m = n - ((1LL << l + 1) - 1);
| ~~^~~
Main.c:51:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
51 | k += (1LL << min(d - y, l) + 1) - 1 - count(d - y + min(d - y, l));
| ~~~~~~~~~~~~~~^~~
Main.c:58:23: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
58 | wl = m >> l + 1 - y_ << y - y_;
| ~~~~~~^~~~
Main.c:58:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
58 | wl = m >> l + 1 - y_ << y - y_;
| ~~^~~~
Main.c:59:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
59 | wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
| ~~^~~~
Main.c:59:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
59 | wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
| ~~~~~~^~~~
Main.c:59:62: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
59 | wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
| ~~~~~~~~~~~~~~~~~~~~^~~
Main.c:61:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
61 | ans = (ans + (power(2, n - (k + (1LL << l + 1 - y_))) - 1)
| ~~~~~~^~~~
Main.c:63:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
63 | ans = (ans + (power(2, n - (k + (m & (1LL << l + 1 - y_) - 1))) - 1)
| ~~~~~~^~~~
Main.c:63:64: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
63 | ans = (ans + (power(2, n - (k + (m & (1LL << l + 1 - y_) - 1))) - 1)
| ~~~~~~~~~~~~~~~~~~~~^~~
Main.c:32:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
Main.c:37:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | 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 |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
10 ms |
288 KB |
Output is correct |
| 12 |
Correct |
10 ms |
304 KB |
Output is correct |
| 13 |
Correct |
9 ms |
212 KB |
Output is correct |
| 14 |
Correct |
9 ms |
212 KB |
Output is correct |
| 15 |
Correct |
9 ms |
212 KB |
Output is correct |
| 16 |
Correct |
9 ms |
212 KB |
Output is correct |
| 17 |
Correct |
9 ms |
288 KB |
Output is correct |
| 18 |
Correct |
8 ms |
212 KB |
Output is correct |
| 19 |
Correct |
9 ms |
212 KB |
Output is correct |
| 20 |
Correct |
9 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
212 KB |
Output is correct |
| 2 |
Correct |
165 ms |
212 KB |
Output is correct |
| 3 |
Correct |
146 ms |
212 KB |
Output is correct |
| 4 |
Correct |
128 ms |
260 KB |
Output is correct |
| 5 |
Correct |
152 ms |
212 KB |
Output is correct |
| 6 |
Correct |
148 ms |
260 KB |
Output is correct |
| 7 |
Correct |
135 ms |
260 KB |
Output is correct |
| 8 |
Correct |
144 ms |
284 KB |
Output is correct |
| 9 |
Correct |
137 ms |
260 KB |
Output is correct |
| 10 |
Correct |
147 ms |
212 KB |
Output is correct |
| 11 |
Execution timed out |
3076 ms |
264 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
212 KB |
Output is correct |
| 2 |
Correct |
149 ms |
272 KB |
Output is correct |
| 3 |
Correct |
128 ms |
212 KB |
Output is correct |
| 4 |
Correct |
131 ms |
212 KB |
Output is correct |
| 5 |
Correct |
153 ms |
280 KB |
Output is correct |
| 6 |
Correct |
150 ms |
212 KB |
Output is correct |
| 7 |
Correct |
145 ms |
212 KB |
Output is correct |
| 8 |
Correct |
153 ms |
212 KB |
Output is correct |
| 9 |
Correct |
143 ms |
268 KB |
Output is correct |
| 10 |
Correct |
153 ms |
272 KB |
Output is correct |
| 11 |
Correct |
556 ms |
212 KB |
Output is correct |
| 12 |
Correct |
556 ms |
212 KB |
Output is correct |
| 13 |
Correct |
573 ms |
272 KB |
Output is correct |
| 14 |
Correct |
573 ms |
268 KB |
Output is correct |
| 15 |
Correct |
572 ms |
272 KB |
Output is correct |
| 16 |
Correct |
574 ms |
284 KB |
Output is correct |
| 17 |
Correct |
542 ms |
212 KB |
Output is correct |
| 18 |
Correct |
543 ms |
212 KB |
Output is correct |
| 19 |
Correct |
543 ms |
268 KB |
Output is correct |
| 20 |
Correct |
544 ms |
272 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 |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
10 ms |
288 KB |
Output is correct |
| 12 |
Correct |
10 ms |
304 KB |
Output is correct |
| 13 |
Correct |
9 ms |
212 KB |
Output is correct |
| 14 |
Correct |
9 ms |
212 KB |
Output is correct |
| 15 |
Correct |
9 ms |
212 KB |
Output is correct |
| 16 |
Correct |
9 ms |
212 KB |
Output is correct |
| 17 |
Correct |
9 ms |
288 KB |
Output is correct |
| 18 |
Correct |
8 ms |
212 KB |
Output is correct |
| 19 |
Correct |
9 ms |
212 KB |
Output is correct |
| 20 |
Correct |
9 ms |
212 KB |
Output is correct |
| 21 |
Correct |
142 ms |
212 KB |
Output is correct |
| 22 |
Correct |
165 ms |
212 KB |
Output is correct |
| 23 |
Correct |
146 ms |
212 KB |
Output is correct |
| 24 |
Correct |
128 ms |
260 KB |
Output is correct |
| 25 |
Correct |
152 ms |
212 KB |
Output is correct |
| 26 |
Correct |
148 ms |
260 KB |
Output is correct |
| 27 |
Correct |
135 ms |
260 KB |
Output is correct |
| 28 |
Correct |
144 ms |
284 KB |
Output is correct |
| 29 |
Correct |
137 ms |
260 KB |
Output is correct |
| 30 |
Correct |
147 ms |
212 KB |
Output is correct |
| 31 |
Execution timed out |
3076 ms |
264 KB |
Time limit exceeded |
| 32 |
Halted |
0 ms |
0 KB |
- |
