제출 #508645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
508645		AugustinasJucas	Spiral (BOI16_spiral)	C++14	31 / 100	2 ms	204 KiB

spiral

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
struct m{
    long long a;
    m(long long x = 0){
        a = x;
    }
    m operator - (m x) const {
        m ret = {a};
        ret.a = (ret.a - x.a + mod) % mod;
        return ret;
    }
    m operator - (long long x) const {
        m ret = {a};
        ret.a = (ret.a - x + mod) % mod;
        return ret;
    }
    m operator + (long long x) const {
        m ret = {a};
        ret.a = (ret.a + x) % mod;
        return ret;
    }
    m operator * (long long x) const {
        m ret = {a};
        ret.a = (ret.a * x) % mod;
        return ret;
    }
    m operator + (m x) const {
        m ret = {a};
        ret.a = (ret.a + x.a) % mod;
        return ret;
    }
    m operator * (m x) const {
        m ret = {a};
        ret.a = ret.a * x.a % mod;
        return ret;
    }
    m operator % (m x) const {
        m ret = {a};
        ret.a = ret.a % x.a % mod;
        return ret;
    }
    m operator % (long long x) const {
        m ret = {a};
        ret.a = ret.a % x % mod;
        return ret;
    }
    m operator = (long long x){
        a = x;
        return *this;
    }
    m operator = (m x){
        a = x.a;
        return *this;
    }
    m operator = (int x){
        a = x;
        return *this;
    }
    bool operator < (long long x) const {
        return a < x;
    }
    bool operator < (m x) const {
        return a < x.a;
    }
    bool operator == (long long x) const {
        return a == x;
    }
    bool operator == (m x) const {
        return a == x.a;
    }
    bool operator != (long long x) const {
        return a != x;
    }
    bool operator != (m x) const {
        return a != x.a;
    }
    bool operator >= (long long x) const {
        return a >= x;
    }
    bool operator >= (m x) const {
        return a >= x.a;
    }

    void print(){
        cout << a;
    }
};
void print(vector<m> f){
    for(m i = 0; i < f.size(); i = i+1){
//        cout << f[i].a << "x^" << i;
//        if(i != f.size()-1) cout << " + ";
    }
}
m pw(m x, m y){
    if(y == 0) return 1;
    auto s = pw(x, y.a / 2);
    s = s * s % mod;
    if(y % 2 == 1) s = s * x % mod;
    return s;
}

m inv(m a){
    return pw(a, mod-2);
}
vector<m> smF2(vector<m> f){    // g(x) = f(0) + f(1) + f(2) + ... + f(x)                                                    // ax^2 + bx + c
    vector<m> ret(4, 0);
    m a = f[2];
    m b = f[1];
    m c = f[0];
    ret[0] = c;
    ret[1] = c + (a + b) * inv(2) - a * inv(3);
    ret[2] = (a + b) * inv(2);
    ret[3] = a * inv(3);
    return ret;
}

vector<m> smF3(vector<m> f){
    vector<m> ret(5, 0);
    m a = f[3];
    m b = f[2];
    m c = f[1];
    m d = f[0];
    ret[0] = d;
    ret[1] = a * inv(4) - (a * 3ll * inv(2) + b) * inv(3) + (a * inv(2) + b + c) * inv(2) + d;
    ret[2] = (a * inv(2) + b + c) * inv(2);
    ret[3] = (a*3ll * inv(2) + b) * inv(3);
    ret[4] = a * inv(4);
    return ret;
}


m f(vector<m> F, m x){
    m ret = 0;
    for(m i = 0; i < F.size(); i = i + 1){
        ret = ret + pw(x, i) * F[i.a];
    }
    return ret;
}
m getSum(vector<m> F, m h, m k){
    m n1 = (h+1) * k * (k-1) * inv(2ll);
    m n2 = f(smF2(F), h) * k;
    return n1 + n2;
}

m getKvad1(){
    return 0;

}
m fff(m a, m b, m c, m d, m x){
    return pw(x, 3)*(a*2ll) + pw(x, 2)*(b*2ll+a+a*d+2) + x*(c*2ll+d*2ll+d*b+b+1) + (c*d + d + c);
}
m FFF(m a, m b, m c, m d, m x){
    if(x == -1) return 0;
    m A = a * inv(2);
    m B = (a*4ll + b*2ll + a*d + 2ll) * inv(3);
    m C = (b + a*2ll + b*2ll + a*d + 2ll + c*2ll + d*2ll + b*d + 1ll) * inv(2);
    m E = c + d + c*d;
    m D = A - B + C + E;
    return pw(x, 4)*A + pw(x, 3) * B + pw(x, 2) * C + pw(x, 1) * D + E;
}

m getFullSum4(m h, m w){ // 4 ketvircio staciakampio suma
    // h - aukstis, w - plotis
    // kvadrato suma
    m ret = FFF(4, 3, 1, 1, min(h.a, w.a-1));
    if(h.a+1 >= w.a){     // vertikalus
//        cout << "vertikalus! " << endl;
//        cout <<  getSum({1, 3, 4}, h, w+1).a << " - " << getSum({1, 3, 4}, w-1, w+1).a << endl;
        ret = ret + getSum({1, 3, 4}, h, w+1) - getSum({1, 3, 4}, w-1, w+1);

    }else{          // horizontalus
        ret = ret + getSum({m(1) - h, m(-3), m(4)}, w, h + m(1)) - getSum({m(1) - h, m(-3), m(4)}, h+m(1), h+m(1));
    }
    return ret;
}
m getFullSum2(m h, m w){
    m ret = FFF(4, -3, 1, 0, min(h, w));;
    if(h.a >= w.a){
//        cout << ret.a << " + " << getSum({m(1), m(-1)-w, m(4)}, h, w+1).a << " - " << getSum({m(1), m(-1)-w, m(4)}, w, w+1).a << endl; 
        ret = ret + getSum({m(1)-w, m(-1), m(4)}, h, w+1) - getSum({m(1)-w, m(-1), m(4)}, w, w+1);
    }else{
        ret = ret + getSum({m(1), m(-3), m(4)}, w, h+1) - getSum({m(1), m(-3), m(4)}, h, h+1);
    }
    return ret;
}
int main() {
    int n, t; cin >> n >> t;
    while(t--){
        int x, y; cin >> x>> y >> x >> y;
//        cout << getFullSum2(y, x).a << endl;
        cout << (getFullSum2(y, x) - getFullSum2(0, x) - getFullSum2(y, 0) + getFullSum2(0, 0)).a << "\n";
    }
    return 0;
    cout << endl << endl;
//    cout << fff(4, -1, 1, 0, 3);
//    cout << FFF(4, -3, 1, 0, 2);
//    cout << fff(4, -3, 1, 0, 2);
    cout << endl << endl;
    print(smF3({1, 3, 1, 2}));
    cout << endl;
    //cout << f(4, 5) - f(4, 3);
    //cout << f(3, 3) - f(3, 2) + 1;
//    cout << kvad(2);
    getSum({m(1), m(3), m(4)}, m(4), m(2));

    return 0;
}

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