oj.uz

Submission #529468

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

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
31.0 / 31.0

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

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -