Submission #529468

#	Time	Username	Problem	Language	Result	Execution time	Memory
529468		KoD	Spiral (BOI16_spiral)	C++17	31 / 100	1 ms	204 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;
        std::cout << solve_simple(x2, y2, Poly({2, -3, 4})).x << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 31 / 31
• Subtask 5: 0 / 25