# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
529483 |
2022-02-23T04:31:03 Z |
KoD |
Spiral (BOI16_spiral) |
C++17 |
|
6 ms |
312 KB |
#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::tuple;
using std::pair;
constexpr int MOD = 1000000007;
struct Fp {
int x;
Fp(int x = 0) : x((x % MOD + MOD) % MOD) {}
Fp& operator+=(const Fp& t) {
if ((x += t.x) >= MOD) x -= MOD;
return *this;
}
Fp& operator-=(const Fp& t) {
if ((x -= t.x) < 0) x += MOD;
return *this;
}
Fp& operator*=(const Fp& t) {
x = (long long)x * t.x % MOD;
return *this;
}
Fp& operator/=(const Fp& t) {
*this *= t.inv();
return *this;
}
Fp operator+(const Fp& t) const {
return Fp(*this) += t;
}
Fp operator-(const Fp& t) const {
return Fp(*this) -= t;
}
Fp operator*(const Fp& t) const {
return Fp(*this) *= t;
}
Fp operator/(const Fp& t) const {
return Fp(*this) /= t;
}
Fp pow(int e) const {
Fp ret(1), mul(*this);
while (e > 0) {
if (e & 1) ret *= mul;
mul *= mul;
e >>= 1;
}
return ret;
}
Fp inv() const {
return pow(MOD - 2);
}
};
using Poly = vector<Fp>;
Fp eval(const Poly& f, const Fp x) {
Fp v = 1, ret = 0;
for (const Fp c : f) {
ret += c * v;
v *= x;
}
return ret;
}
Poly operator+(const Poly& f, const Poly& g) {
const int n = f.size(), m = g.size();
Poly ret(std::max(n, m));
for (int i = 0; i < n; ++i) {
ret[i] += f[i];
}
for (int i = 0; i < m; ++i) {
ret[i] += g[i];
}
return ret;
}
Poly operator-(const Poly& f, const Poly& g) {
const int n = f.size(), m = g.size();
Poly ret(std::max(n, m));
for (int i = 0; i < n; ++i) {
ret[i] += f[i];
}
for (int i = 0; i < m; ++i) {
ret[i] -= g[i];
}
return ret;
}
Poly operator*(const Poly& f, const Poly& g) {
const int n = f.size(), m = g.size();
if (n == 0 or m == 0) return {};
Poly ret(n + m - 1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
ret[i + j] += f[i] * g[j];
}
}
return ret;
}
Poly operator*(const Poly& f, const Fp& c) {
Poly ret = f;
for (auto& x : ret) {
x *= c;
}
return ret;
}
Poly prefix_sum(const Poly& p) {
const int n = p.size();
vector<Fp> sum(n + 1);
for (int x = 1; x <= n; ++x) {
sum[x] = sum[x - 1] + eval(p, x);
}
Poly ret;
for (int x = 0; x <= n; ++x) {
Poly f = {1};
for (int y = 0; y <= n; ++y) {
if (y != x) {
f = f * Poly({-y, 1});
}
}
ret = ret + f * (sum[x] / eval(f, x));
}
return ret;
}
Fp solve_simple(int x, int y, const Poly& base) {
const Poly f = prefix_sum((base + Poly({-1, 1})) * Poly({-1, 2}));
if (x <= y) {
const Poly g = prefix_sum((base + Poly({-2, 2})) * x - Poly({Fp(x) * Fp(x - 1) / 2}));
return eval(f, x) + eval(g, y) - eval(g, x);
} else {
const Poly g = prefix_sum(base * y + Poly({Fp(y) * Fp(y - 1) / 2}));
return eval(f, y) + eval(g, x) - eval(g, y);
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, Q;
std::cin >> N >> Q;
while (Q--) {
int x1, y1, x2, y2;
std::cin >> x1 >> y1 >> x2 >> y2;
Poly base = {2, -3, 4};
Fp ret = x1 <= 0 and y1 <= 0 and x2 >= 0 and y2 >= 0 ? 1 : 0;
for (int step = 0; step < 3; ++step) {
if (x2 >= 1 and y2 >= 1) {
ret += solve_simple(x2, y2, base);
const int a = std::max(x1 - 1, 0);
const int b = std::max(y1 - 1, 0);
ret -= solve_simple(a, y2, base);
ret -= solve_simple(x2, b, base);
ret += solve_simple(a, b, base);
}
if (y1 <= 0 and y2 >= 0 and x2 >= 1) {
const auto tmp = prefix_sum(base - Poly{1});
ret += eval(tmp, x2);
ret -= eval(tmp, std::max(x1 - 1, 0));
}
base[1] += 2;
std::swap(x1, y1);
std::swap(x2, y2);
std::swap(y1, y2);
y1 = -y1;
y2 = -y2;
}
if (y1 <= 0 and y2 >= 0 and x2 >= 1) {
const auto tmp = prefix_sum(base - Poly{1});
ret += eval(tmp, x2);
ret -= eval(tmp, std::max(x1 - 1, 0));
}
base[0] += 1;
y1 -= 1, y2 -= 1;
if (x2 >= 1 and y2 >= 1) {
ret += solve_simple(x2, y2, base);
const int a = std::max(x1 - 1, 0);
const int b = std::max(y1 - 1, 0);
ret -= solve_simple(a, y2, base);
ret -= solve_simple(x2, b, base);
ret += solve_simple(a, b, base);
}
if (y1 <= 0 and y2 >= 0 and x2 >= 1) {
const auto tmp = prefix_sum(base - Poly{1});
ret += eval(tmp, x2);
ret -= eval(tmp, std::max(x1 - 1, 0));
}
std::cout << ret.x << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
204 KB |
Output is correct |
2 |
Correct |
6 ms |
304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
204 KB |
Output is correct |
3 |
Correct |
6 ms |
304 KB |
Output is correct |
4 |
Correct |
3 ms |
204 KB |
Output is correct |
5 |
Correct |
5 ms |
312 KB |
Output is correct |