oj.uz

Submission #529483

# Submission time Handle Problem Language Result Execution time Memory
529483 2022-02-23T04:31:03 Z KoD Spiral (BOI16_spiral) C++17
100 / 100
 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;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB Output is correct
2 Correct 6 ms 304 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct

Subtask #5
25.0 / 25.0

# 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