| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 78788 |
2018-10-08T18:51:49 Z |
scanhex |
Spiral (BOI16_spiral) |
C++17 |
|
2 ms |
616 KB |
#include <bits/stdc++.h>
using namespace std;
using nagai = long long;
using ll = long long;
const nagai mod = 1e9 + 7;
nagai sumx(nagai x)
{
return x * (x + 1) / 2 % mod;
}
nagai calc11(nagai x, nagai y, nagai i)
{
nagai j = 4 * i * i % mod;
return sumx(j + i - x) - sumx((j - i - y) - 1);
}
nagai md(nagai x)
{
x %= mod;
if (x < 0)
x += mod;
return x;
}
nagai mult(nagai a, nagai b)
{
return (a * b) % mod;
}
nagai pw(nagai a, nagai b)
{
nagai c = 1;
while (b)
{
if (b & 1)
c = mult(c, a);
a = mult(a, a);
b >>= 1;
}
return c;
}
nagai inv(nagai x)
{
return pw(x, mod - 2);
}
nagai add(nagai a, nagai b)
{
a += b;
return a >= mod ? a - mod : a;
}
nagai integrate(nagai n, nagai c0 = 0, nagai c1 = 0, nagai c2 = 0, nagai c3 = 0)
{
static nagai inv30 = inv(30);
static nagai inv6 = inv(6);
static nagai inv2 = (mod + 1) / 2;
static nagai inv4 = mult(inv2, inv2);
nagai ans = mult(c3, mult(inv4, mult(n, mult(n, mult(n + 1, n + 1)))));
ans = add(ans, mult(c2, mult(inv6, mult(n, mult(n + 1, 2 * n + 1)))));
ans = add(ans, mult(c1, mult(inv2, mult(n, n + 1))));
ans = add(ans, mult(c0, n));
return ans;
}
nagai sum11(nagai x, nagai y, nagai i)
{
nagai c3 = 16;
nagai c2 = (8 * x + 8 * y + 8) % mod;
nagai c1 = md(2 * x - 2 * y);
nagai c0 = md(x * x + x - y * y - y);
return integrate(i, c0, c1, c2, c3);
}
nagai sum11(nagai x, nagai y, nagai from, nagai to)
{
nagai ans = sum11(x, y, to) - (from == 0 ? 0 : sum11(x, y, from - 1));
if (ans < 0)
ans += mod;
return ans;
}
nagai sum21(nagai x, nagai i)
{
nagai c0 = 0, c1 = md(-2 - 4 * x), c2 = md(16 * x), c3 = 32;
return integrate(i, c0, c1, c2, c3);
}
nagai sum12(nagai y, nagai i)
{
nagai c0 = 0, c1 = md(4 * y + 2), c2 = md(16 * y + 4 + 4 + 9 - 1), c3 = 32;
return integrate(i, c0, c1, c2, c3);
}
nagai sum21(nagai x, nagai from, nagai to)
{
return md(sum21(x, to) - sum21(x, from - 1));
}
nagai sum12(nagai y, nagai from, nagai to)
{
return md(sum12(y, to) - sum12(y, from - 1));
}
nagai sum22(nagai i)
{
nagai c0 = 0, c1 = 8, c2 = 0, c3 = 64;
return integrate(i, c0, c1, c2, c3);
}
nagai sum22(nagai from, nagai to)
{
return md(sum22(to) - sum22(from - 1));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
auto get = [&](int x, int y)
{
if (x < -n || y < -n)
return 0LL;
nagai ans = mult(2, mult(x + n + 1, y + n + 1));
// -i <= x < i, -i <= y < i
int from = 0;
int to = n;
if (x < 0)
from = max(from, -x);
if (y < 0)
from = max(from, -y);
if (x >= 0)
from = max(from, x + 1);
if (y >= 0)
from = max(from, y + 1);
if (from <= to)
ans = add(ans, sum11(x, y, from, to));
to = n; // to = from - 1
from = 0;
if (x <= y)
{
// y >= i
// x < i
// -i <= x
from = max(0, x + 1);
to = y;
from = max(from, -x);
if (from <= to)
ans = add(ans, sum21(x, from, to));
}
else
{
from = max(0, y + 1);
to = x;
from = max(from, -y);
if (from <= to)
ans = add(ans, sum12(y, from, to));
}
// y >= i
// x >= i
from = 0;
to = min(x, y);
if (from <= to)
ans = add(ans, sum22(from, to));
return ans;
};
auto transform = [&](int& x, int& y)
{
y = -y;
swap(x, y);
};
while (q--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
transform(x1, y1);
transform(x2, y2);
if (x1 > x2)
swap(x1, x2);
if (y1 > y2)
swap(y1, y2);
--x1, --y1;
//cerr << get(x2, y2) << ' ' << get(x2, y1) << ' ' << get(x1, y2) << ' ' << get(x1, y1) << '\n';
nagai ans = get(x2, y2) - get(x2, y1) - get(x1, y2) + get(x1, y1);
ans = md(ans);
ans = mult(ans, (mod + 1) / 2);
cout << ans << '\n';
}
/*
int n;
cin >> n;
int x = n, y = n;
vector<int> dx = {0, -1, 0, 1};
vector<int> dy = {1, 0, -1, 0};
int curd = 0;
vector<vector<int>> board(2 * n + 1, vector<int>(2 * n + 1));
int cur = 0;
for (int i = 0; i < 4 * n + 1; ++i)
{
int len = i / 2 + 1;
for (int j = 0; j < len; ++j)
{
board[x][y] = cur++;
x += dx[curd];
y += dy[curd];
}
++curd;
curd %= 4;
}
cerr << sum11(0, 0, 1, 1) << '\n';
cerr << sum11(0, 0, 2, 2) << '\n';
cerr << sum11(0, 1, 2, 2) << '\n';
// cerr << sum21(0, 2, 2) << '\n';
// cerr << sum12(0, 1, 1) << '\n';
// cerr << sum22(0, 2) << '\n';
*/
return 0;
}
Compilation message
spiral.cpp: In function 'nagai integrate(nagai, nagai, nagai, nagai, nagai)':
spiral.cpp:60:15: warning: unused variable 'inv30' [-Wunused-variable]
static nagai inv30 = inv(30);
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
472 KB |
Output is correct |
| 3 |
Correct |
2 ms |
472 KB |
Output is correct |
| 4 |
Correct |
2 ms |
580 KB |
Output is correct |
| 5 |
Correct |
2 ms |
616 KB |
Output is correct |
