| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 831005 |
2023-08-19T14:53:48 Z |
rainboy |
Party (INOI20_party) |
C |
|
3000 ms |
412 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 int 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 |
1 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 |
1 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 |
135 ms |
276 KB |
Output is correct |
| 2 |
Correct |
158 ms |
272 KB |
Output is correct |
| 3 |
Correct |
142 ms |
272 KB |
Output is correct |
| 4 |
Correct |
122 ms |
268 KB |
Output is correct |
| 5 |
Correct |
144 ms |
212 KB |
Output is correct |
| 6 |
Correct |
140 ms |
268 KB |
Output is correct |
| 7 |
Correct |
130 ms |
212 KB |
Output is correct |
| 8 |
Correct |
135 ms |
272 KB |
Output is correct |
| 9 |
Correct |
130 ms |
212 KB |
Output is correct |
| 10 |
Correct |
142 ms |
276 KB |
Output is correct |
| 11 |
Execution timed out |
3055 ms |
412 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
268 KB |
Output is correct |
| 2 |
Correct |
148 ms |
268 KB |
Output is correct |
| 3 |
Correct |
128 ms |
272 KB |
Output is correct |
| 4 |
Correct |
131 ms |
272 KB |
Output is correct |
| 5 |
Correct |
146 ms |
272 KB |
Output is correct |
| 6 |
Correct |
142 ms |
268 KB |
Output is correct |
| 7 |
Correct |
140 ms |
268 KB |
Output is correct |
| 8 |
Correct |
146 ms |
272 KB |
Output is correct |
| 9 |
Correct |
135 ms |
272 KB |
Output is correct |
| 10 |
Correct |
146 ms |
276 KB |
Output is correct |
| 11 |
Correct |
559 ms |
212 KB |
Output is correct |
| 12 |
Correct |
558 ms |
332 KB |
Output is correct |
| 13 |
Correct |
573 ms |
272 KB |
Output is correct |
| 14 |
Correct |
574 ms |
272 KB |
Output is correct |
| 15 |
Correct |
574 ms |
284 KB |
Output is correct |
| 16 |
Correct |
574 ms |
268 KB |
Output is correct |
| 17 |
Correct |
543 ms |
272 KB |
Output is correct |
| 18 |
Correct |
544 ms |
268 KB |
Output is correct |
| 19 |
Correct |
544 ms |
272 KB |
Output is correct |
| 20 |
Correct |
543 ms |
276 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 |
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 |
1 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 |
135 ms |
276 KB |
Output is correct |
| 22 |
Correct |
158 ms |
272 KB |
Output is correct |
| 23 |
Correct |
142 ms |
272 KB |
Output is correct |
| 24 |
Correct |
122 ms |
268 KB |
Output is correct |
| 25 |
Correct |
144 ms |
212 KB |
Output is correct |
| 26 |
Correct |
140 ms |
268 KB |
Output is correct |
| 27 |
Correct |
130 ms |
212 KB |
Output is correct |
| 28 |
Correct |
135 ms |
272 KB |
Output is correct |
| 29 |
Correct |
130 ms |
212 KB |
Output is correct |
| 30 |
Correct |
142 ms |
276 KB |
Output is correct |
| 31 |
Execution timed out |
3055 ms |
412 KB |
Time limit exceeded |
| 32 |
Halted |
0 ms |
0 KB |
- |
