| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 635481 |
2022-08-26T10:21:57 Z |
Cyanmond |
Party (INOI20_party) |
C++17 |
|
3000 ms |
788512 KB |
#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 mod = 1000000007;
i64 nmr(i64 a) {
a %= mod;
if (a < 0) a += mod;
return a;
}
i64 add(i64 a, i64 b) {
a += b;
if (a > mod) a -= mod;
return a;
}
i64 mul(i64 a, i64 b) { return a * b % mod; }
void add_m(i64 &a, i64 b) { a = add(a, b); }
void mul_m(i64 &a, i64 b) { a = mul(a, b); }
i64 inv(i64 x) {
i64 a = x, b = mod, u = 1, v = 0, t = 0;
while (b > 0) {
t = a / b;
a -= t * b;
u -= t * v;
std::swap(a, b);
std::swap(u, v);
}
return nmr(u);
}
std::array<i64, 100> p2m;
void init_p2() {
p2m[0] = 2;
for (int i = 0; i < 90; ++i) p2m[i + 1] = mul(p2m[i], p2m[i]);
}
std::unordered_map<i64, i64> p2memo;
i64 pow2(i64 n) {
// if (p2memo.find(n) != p2memo.end()) return p2memo[n];
i64 ret = 1;
int i = 0;
while (n != 0) {
if (n & 1) mul_m(ret, p2m[i]);
++i;
n >>= 1;
}
// return p2memo[n2] = ret;
return ret;
}
std::vector<std::tuple<i64, i64, int>> evs;
void solve(const i64 N, const int q_id) {
// Time Complexity O(log^4 N)
// N = 2 ^ k - 1
i64 k = 0;
while ((1ll << k) - 1 < N) ++k;
// assert((1ll << k) - 1 == N);
std::vector<i64> red_vs = {N};
while (red_vs.back() != 1) {
red_vs.push_back(red_vs.back() / 2);
}
std::reverse(red_vs.begin(), red_vs.end());
std::vector<std::vector<i64>> red_count_vs(k);
for (int i = k - 1; i >= 0; --i) {
red_count_vs[i].assign(k - i, 0);
red_count_vs[i][0] = 1;
for (int j = 1; j < k - i; ++j) red_count_vs[i][j] += red_count_vs[i + 1][j - 1];
if (i != k - 1 and red_vs[i + 1] == 2 * red_vs[i] + 1) {
for (int j = 1; j < k - i; ++j) red_count_vs[i][j] += 1ll << (j - 1);
} else {
for (int j = 1; j < k - i - 1; ++j) red_count_vs[i][j] += 1ll << (j - 1);
}
}
// sa0te
auto dfs = [&](auto &&self, const int d, const i64 v) -> i64 {
if (v > N) return 0;
i64 ret = 0;
if (red_vs[d] == v) {
// rec
add_m(ret, self(self, d + 1, 2 * v));
add_m(ret, self(self, d + 1, 2 * v + 1));
i64 sum = 0;
for (int u = 0; u <= 2 * k; ++u) {
i64 count_v = 0;
for (i64 p = 0; p <= u; ++p) {
const i64 now_d = d - p;
if (now_d < 0) continue;
const i64 t = u - p;
if (now_d + t >= k) continue;
if (t == 0)
++count_v;
else {
if (p == 0)
count_v += red_count_vs[now_d][t];
else
count_v += red_count_vs[now_d][t] - red_count_vs[now_d + 1][t - 1];
}
}
if (count_v == 0) continue;
const i64 ks = u;
evs.push_back({N - sum, ks, q_id});
evs.push_back({N - sum - count_v, -ks, q_id});
sum += count_v;
}
} else {
// no rec
i64 v2 = v;
for (int fd = d; fd < k; ++fd) {
if (v * (1ll << (fd - d)) > N) continue;
const i64 ms = nmr(1ll << (fd - d));
i64 sum = 0;
for (int u = 0; u <= fd + k; ++u) {
i64 count_v = 0;
bool h = false;
for (int p = 0; p <= std::min(u, fd); ++p) {
const int now_d = fd - p;
bool th = false;
if (red_vs[now_d] == v2 / (1ll << p)) th = true;
const int t = u - p;
if (now_d + t >= k) {
if (th) h = true;
continue;
}
if (th) {
if (t == 0)
++count_v;
else {
if (h)
count_v +=
red_count_vs[now_d][t] - red_count_vs[now_d + 1][t - 1];
else
count_v += red_count_vs[now_d + 1][t - 1];
}
h = true;
} else {
if (v % 2 == 1 and now_d + t == k - 1) continue;
count_v += 1ll << (p != 0 and t != 0 ? t - 1 : t);
}
}
if (count_v == 0) continue;
const i64 ks = mul(ms, u);
evs.push_back({N - sum, ks, q_id});
evs.push_back({N - sum - count_v, -ks, q_id});
sum += count_v;
}
v2 *= 2;
}
}
return ret;
};
const auto res = dfs(dfs, 0, 1);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
init_p2();
int Q;
std::cin >> Q;
std::vector<i64> invs(Q);
for (int i = 0; i < Q; ++i) {
i64 N; std::cin >> N;
solve(N, i);
invs[i] = inv(add(pow2(N), mod - 1));
}
std::sort(evs.begin(), evs.end());
std::vector<i64> answer(Q);
i64 now_v = 1, last = 0;
for (const auto &[t, k, i] : evs) {
mul_m(now_v, pow2(t - last));
add_m(answer[i], mul(now_v, nmr(k)));
last = t;
}
for (int i = 0; i < Q; ++i) std::cout << mul(answer[i], invs[i]) << std::endl;
}
Compilation message
Main.cpp: In function 'void solve(i64, int)':
Main.cpp:165:16: warning: unused variable 'res' [-Wunused-variable]
165 | const auto res = dfs(dfs, 0, 1);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1996 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1996 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 10 |
Correct |
8 ms |
1996 KB |
Output is correct |
| 11 |
Correct |
206 ms |
49680 KB |
Output is correct |
| 12 |
Correct |
201 ms |
49700 KB |
Output is correct |
| 13 |
Correct |
189 ms |
49692 KB |
Output is correct |
| 14 |
Correct |
191 ms |
49760 KB |
Output is correct |
| 15 |
Correct |
188 ms |
49616 KB |
Output is correct |
| 16 |
Correct |
191 ms |
49688 KB |
Output is correct |
| 17 |
Correct |
189 ms |
49728 KB |
Output is correct |
| 18 |
Correct |
180 ms |
49644 KB |
Output is correct |
| 19 |
Correct |
180 ms |
49632 KB |
Output is correct |
| 20 |
Correct |
179 ms |
49648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3109 ms |
788512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3091 ms |
394376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1996 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1996 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1996 KB |
Output is correct |
| 10 |
Correct |
8 ms |
1996 KB |
Output is correct |
| 11 |
Correct |
206 ms |
49680 KB |
Output is correct |
| 12 |
Correct |
201 ms |
49700 KB |
Output is correct |
| 13 |
Correct |
189 ms |
49692 KB |
Output is correct |
| 14 |
Correct |
191 ms |
49760 KB |
Output is correct |
| 15 |
Correct |
188 ms |
49616 KB |
Output is correct |
| 16 |
Correct |
191 ms |
49688 KB |
Output is correct |
| 17 |
Correct |
189 ms |
49728 KB |
Output is correct |
| 18 |
Correct |
180 ms |
49644 KB |
Output is correct |
| 19 |
Correct |
180 ms |
49632 KB |
Output is correct |
| 20 |
Correct |
179 ms |
49648 KB |
Output is correct |
| 21 |
Execution timed out |
3109 ms |
788512 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
