#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint MOD = 1e9 + 7;
lint Power(lint x, lint y) {
if (y == 0) return 1;
lint res = Power(x, y / 2);
res = res * res % MOD;
if (y & 1) res = res * x % MOD;
return res;
}
lint Inverse(lint x) {
return Power(x, MOD - 2);
}
using Poly = vector<lint>;
Poly operator + (const Poly &a, const Poly &b) {
Poly c(max(a.size(), b.size()), 0);
for (int i = 0; i < (int) a.size(); i++) {
c[i] += a[i];
}
for (int i = 0; i < (int) b.size(); i++) {
c[i] += b[i];
}
for (int i = 0; i < (int) c.size(); i++) {
c[i] %= MOD;
}
return c;
}
Poly operator - (const Poly &a, const Poly &b) {
Poly c(max(a.size(), b.size()), 0);
for (int i = 0; i < (int) a.size(); i++) {
c[i] += a[i];
}
for (int i = 0; i < (int) b.size(); i++) {
c[i] -= b[i];
}
for (int i = 0; i < (int) c.size(); i++) {
c[i] %= MOD;
}
return c;
}
Poly operator * (const Poly &a, const Poly &b) {
Poly c((int) a.size() + b.size() - 1, 0);
for (int i = 0; i < (int) a.size(); i++) {
for (int j = 0; j < (int) b.size(); j++) {
c[i + j] += a[i] * b[j] % MOD;
}
}
for (int i = 0; i < (int) c.size(); i++) {
c[i] %= MOD;
}
return c;
}
Poly operator * (const Poly &a, const lint &b) {
Poly res = a;
for (auto &i : res) {
i *= b;
i %= MOD;
}
return res;
}
Poly Interpolate(const vector<lint> &X, const vector<lint> &Y) {
Poly res;
for (int i = 0; i < (int) X.size(); i++) {
Poly prod = {1};
lint divis = 1;
for (int j = 0; j < (int) X.size(); j++) if (i != j) {
divis = divis * (X[i] - X[j]) % MOD;
Poly cur = {MOD - X[j], 1};
prod = prod * cur;
}
res = res + prod * (Inverse(divis) * Y[i] % MOD);
}
return res;
}
lint Evaluate(const Poly &p, const lint &x) {
lint cur = 1, res = 0;
for (int i = 0; i < (int) p.size(); i++) {
res += p[i] * cur % MOD;
cur = cur * x % MOD;
}
res %= MOD;
return res;
}
lint Sum(lint L, lint R) {
return (R - L + 1) * (L + R) / 2 % MOD;
}
lint Line(lint AL, lint AR, lint BL, lint BR, lint val) {
lint L = max(AL, BL);
lint R = min(AR, BR);
if (L <= R) {
return (Sum(L - AL + 1, R - AL + 1) + ((R - L + 1) * val % MOD)) % MOD;
}
return 0;
}
lint Layer(lint L, lint X1, lint Y1, lint X2, lint Y2) {
if (L == 0) return (X1 <= 0 && 0 <= X2 && Y1 <= 0 && 0 <= Y2);
lint res = 0;
lint val = 1ll * (2 * L + 1) * (2 * L + 1) % MOD;
val -= 2 * L;
if (Y1 <= -L && -L <= Y2) {
res += Line(-L + 1, L, X1, X2, val);
}
val -= 2 * L;
if (X1 <= -L && -L <= X2) {
res += Line(-L + 1, L, -Y2, -Y1, val);
}
val -= 2 * L;
if (Y1 <= L && L <= Y2) {
res += Line(-L + 1, L, -X2, -X1, val);
}
val -= 2 * L;
if (X1 <= L && L <= X2) {
res += Line(-L + 1, L, Y1, Y2, val);
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
lint N, Q;
cin >> N >> Q;
while (Q--) {
vector<lint> x(4);
for (int i = 0; i < 4; i++) {
cin >> x[i];
}
vector<lint> events = {0};
for (int i = 0; i < 4; i++) {
for (int j = -1; j <= 1; j++) {
events.emplace_back(abs(x[i]) + j);
}
}
sort(begin(events), end(events));
events.resize(unique(begin(events), end(events)) - begin(events));
lint ans = 0;
for (int i = 0; i + 1 < (int) events.size(); i++) {
if (events[i] < 0) continue;
int k = events[i + 1] - events[i];
const int DEG = 4;
if (k >= DEG) {
vector<lint> X(DEG), Y(DEG);
for (int j = 0; j < DEG; j++) {
X[j] = j;
Y[j] = Layer(events[i] + j, x[0], x[1], x[2], x[3]);
}
Poly p = Interpolate(X, Y);
ans += Evaluate(p, k);
} else {
for (int j = events[i]; j < events[i + 1]; j++) {
ans += Layer(j, x[0], x[1], x[2], x[3]);
}
}
}
ans %= MOD;
ans = (ans + MOD) % MOD;
cout << ans << "\n";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
