| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 257003 |
2020-08-03T13:47:46 Z |
Berted |
Spiral (BOI16_spiral) |
C++14 |
|
1 ms |
384 KB |
#include <iostream>
#include <assert.h>
#define ll long long
#define int ll
using namespace std;
const ll MD = 1e9 + 7;
ll pw(ll b, ll e)
{
e = (e + MD - 1) % (MD - 1);
ll t = 1;
while (e)
{
if (e & 1) {t = (t * b) % MD;}
b = (b * b) % MD; e >>= 1;
}
return t;
}
ll trs[5][4] =
{
{0, 0, 0, 0},
{1, pw(2, -1), pw(6, -1), 0},
{0, pw(2, -1), pw(2, -1), pw(4, -1)},
{0, 0, pw(3, -1), pw(2, -1)},
{0, 0, 0, pw(4, -1)}
};
struct poly
{
ll c[5] = {};
poly() {}
poly(int x) {c[0] = (MD + x) % MD;}
poly(int x, int y, int z) {c[2] = (MD + x) % MD; c[1] = (MD + y) % MD; c[0] = (MD + z) % MD;}
};
poly operator+(const poly &a, const poly &b)
{
poly ret;
for (int i = 0; i < 5; i++)
{
ret.c[i] = (a.c[i] + b.c[i]) % MD;
}
return ret;
}
poly operator-(const poly &a, const poly &b)
{
poly ret;
for (int i = 0; i < 5; i++)
{
ret.c[i] = (a.c[i] + MD - b.c[i]) % MD;
}
return ret;
}
poly operator*(const poly &a, const poly &b)
{
poly ret;
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
if (i + j < 5) {ret.c[i + j] = (ret.c[i + j] + a.c[i] * b.c[j] % MD) % MD;}
}
}
return ret;
}
poly raisePoly(const poly &a)
{
poly ret;
for (int i = 1; i < 5; i++)
{
for (int j = 0; j < 4; j++)
{
ret.c[i] = (ret.c[i] + trs[i][j] * a.c[j] % MD) % MD;
}
}
return ret;
}
ll evalPoly(const poly &p, ll x)
{
ll ret = 0, k = 1;
for (int i = 0; i < 5; i++)
{
ret = (ret + p.c[i] * k % MD) % MD;
k = (k * x) % MD;
}
return ret;
}
inline ll UR(int x, int y)
{
poly a = poly(4, -9, 6) * poly(4, -9, 7) * poly(pw(2, -1));
poly b = poly(4, -11, 7) * poly(4, -11, 8) * poly(pw(2, -1));
poly r = raisePoly(a - b);
ll ret = evalPoly(r, min(x, y) + 1);
if (x < y)
{
b = poly(4, -9, 6 - x) * poly(4, -9, 5 - x) * poly(pw(2, -1));
r = raisePoly(a - b);
ret += evalPoly(r, y + 1) - evalPoly(r, x + 1);
}
else
{
a = poly(4, -11, 8 + y) * poly(4, -11, 9 + y) * poly(pw(2, -1));
r = raisePoly(a - b);
ret += evalPoly(r, x + 1) - evalPoly(r, y + 1);
}
ret = (ret % MD + MD) % MD;
return ret;
}
inline ll UL(int x, int y)
{
x = -x;
poly a = poly(4, -7, 4) * poly(4, -7, 5) * poly(pw(2, -1));
poly b = poly(4, -9, 5) * poly(4, -9, 6) * poly(pw(2, -1));
poly r = raisePoly(a - b);
ll ret = evalPoly(r, min(x, y) + 1);
if (x < y)
{
a = poly(4, -9, x + 6) * poly(4, -9, x + 7) * poly(pw(2, -1));
r = raisePoly(a - b);
ret += evalPoly(r, y + 1) - evalPoly(r, x + 1);
}
else
{
b = poly(4, -7, 4 - y) * poly(4, -7, 3 - y) * poly(pw(2, -1));
r = raisePoly(a - b);
ret += evalPoly(r, x + 1) - evalPoly(r, y + 1);
}
a = raisePoly(poly(4, -9, 6));
ret -= evalPoly(a, y + 1);
ret = (ret % MD + MD) % MD;
return ret;
}
inline ll DL(int x, int y)
{
x = -x; y = -y;
poly a = poly(4, -5, 2) * poly(4, -5, 3) * poly(pw(2, -1));
poly b = poly(4, -7, 4) * poly(4, -7, 3) * poly(pw(2, -1));
poly r = raisePoly(a - b);
ll ret = evalPoly(r, min(x, y) + 1);
if (x < y)
{
b = poly(4, -5, 2 - x) * poly(4, -5, 1 - x) * poly(pw(2, -1));
r = raisePoly(a - b);
ret += evalPoly(r, y + 1) - evalPoly(r, x + 1);
}
else
{
a = poly(4, -7, 4 + y) * poly(4, -7, 5 + y) * poly(pw(2, -1));
r = raisePoly(a - b);
ret += evalPoly(r, x + 1) - evalPoly(r, y + 1);
}
a = raisePoly(poly(4, -7, 4));
ret -= evalPoly(a, x + 1);
ret = (ret % MD + MD) % MD;
return ret;
}
inline ll DR(int x, int y)
{
y = -y;
ll ret = 0;
poly a = raisePoly(poly(4, 3, 2)), b, r;
ret = evalPoly(a, y); x--;
if (x)
{
a = poly(4, 5, 1) * poly(4, 5, 2) * poly(pw(2, -1));
b = poly(4, 3, 3) * poly(4, 3, 2) * poly(pw(2, -1));
r = raisePoly(a - b);
ret += evalPoly(r, min(x, y));
if (x < y)
{
a = poly(4, 3, 3 + x) * poly(4, 3, 2 + x) * poly(pw(2, -1));
r = raisePoly(a - b);
ret += evalPoly(r, y) - evalPoly(r, x);
}
else
{
b = poly(4, 5, 2 - y) * poly(4, 5, 1 - y) * poly(pw(2, -1));
r = raisePoly(a - b);
ret += evalPoly(r, x) - evalPoly(r, y);
}
}
ret = (ret % MD + MD) % MD;
return ret;
}
int32_t main()
{
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, q; cin >> n >> q;
for (int i = 0; i < q; i++)
{
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
ll res = 0;
int px1 = max(x1, 0LL), px2 = x2;
int py1 = max(y1, 0LL), py2 = y2;
if (px1 <= px2 && py1 <= py2)
{
//cout << "UR " << px1 << " " << py1 << " " << px2 << " " << py2 << "\n";
res += UR(px2, py2);
if (px1) {res -= UR(px1 - 1, py2);}
if (py1) {res -= UR(px2, py1 - 1);}
if (px1 && py1) {res += UR(px1 - 1, py1 - 1);}
//cout << res << "\n";
}
px1 = x1; px2 = min(-1LL, x2);
py1 = max(0LL, y1); py2 = y2;
if (px1 <= px2 && py1 <= py2)
{
//cout << "UL " << px1 << " " << py1 << " " << px2 << " " << py2 << "\n";
res += UL(px1, py2);
if (py1) {res -= UL(px1, py1 - 1);}
if (px2 < -1) {res -= UL(px2 + 1, py2);}
if (py1 && px2 < -1) {res += UL(px2 + 1, py1 - 1);}
//cout << res << "\n";
}
px1 = x1; px2 = min(0LL, x2);
py1 = y1; py2 = min(-1LL, y2);
if (px1 <= px2 && py1 <= py2)
{
//cout << "DL " << px1 << " " << py1 << " " << px2 << " " << py2 << "\n";
res += DL(px1, py1);
if (py2 < -1) {res -= DL(px1, py2 + 1);}
if (px2 < 0) {res -= DL(px2 + 1, py1);}
if (py2 < -1 && px2 < 0) {res += DL(px2 + 1, py2 + 1);}
//cout << res << "\n";
}
px1 = max(1LL, x1); px2 = x2;
py1 = y1; py2 = min(-1LL, y2);
if (px1 <= px2 && py1 <= py2)
{
//cout << "DR " << px1 << " " << py1 << " " << px2 << " " << py2 << "\n";
res += DR(px2, py1);
if (py2 < -1) {res -= DR(px2, py2 + 1);}
if (px1 > 1) {res -= DR(px1 - 1, py1);}
if (py2 < -1 && px1 > 1) {res += DR(px1 - 1, py2 + 1);}
//cout << res << "\n";
}
cout << (res % MD + MD) % MD << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
