Submission #529483

#	Time	Username	Problem	Language	Result	Execution time	Memory
529483		KoD	Spiral (BOI16_spiral)	C++17	100 / 100	6 ms	312 KiB

spiral

#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 / 12
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 31 / 31
• Subtask 5: 25 / 25