QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#143405 | #6673. Be Careful 2 | zhaohaikun | TL | 160ms | 3664kb | C++14 | 3.8kb | 2023-08-21 11:00:05 | 2023-08-21 11:00:06 |
Judging History
answer
#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
const int N = 5010, MOD = 998244353;
int n, m, k, ans;
pair <int, int> a[N];
int inv[10];
void init(int x) {
inv[1] = 1;
F(i, 2, x) inv[i] = (ll) (MOD - MOD / i) * inv[MOD % i] % MOD;
}
void add(int &x, int y) { if ((x += y) >= MOD) x -= MOD; }
struct Lagrange {
int n, y[10];
inline void init(int nn) {
n = nn;
F(i, 1, n + 1) {
int t = 1;
F(j, 1, n) t = (ll) t * i % MOD;
y[i] = (y[i - 1] + t) % MOD;
}
}
inline int query(int x) {
int ans = 0;
F(i, 1, n + 1) {
int t = y[i];
F(j, 0, n + 1) if (j != i) t = (ll) t * (x - j + MOD) % MOD * (i > j ? inv[i - j] : (MOD - inv[j - i])) % MOD;
add(ans, t);
}
return ans;
}
} t[10];
int calc(int n, int m) {
if (n < 0 || m < 0) return 0;
int k = min(n, m);
int ans = (t[4].query(k) - (ll) t[3].query(k) * (n + m + 2) % MOD + MOD + (ll) t[2].query(k) * (((ll) n * m + n + m + 1) % MOD)) % MOD;
return ans;
}
int calc1(int x, int y, int n, int m) {
return ((ll) calc(n, m) - calc(x, m) - calc(n, y) - calc(n - x, m) - calc(n, m - y) + calc(x, y) + calc(n - x, y) + calc(x, m - y) + calc(n - x, m - y) + MOD * 4ll) % MOD;
}
int query(int kx, int ky, int tx, int ty) {
return ((ll) calc1(tx, ty, n, m) - calc1(tx - kx, ty, n - kx, m) - calc1(tx, ty - ky, n, m - ky) + calc1(tx - kx, ty - ky, n - kx, m - ky) + MOD * 2) % MOD;
}
signed main() {
init(5);
F(i, 2, 4) t[i].init(i);
read(n), read(m), read(k);
add(ans, calc(n, m));
F(i, 1, k) read(a[i].first), read(a[i].second);
sort(a + 1, a + k + 1);
F(i, 1, k) {
int bg = 2e9, sm = -2e9;
add(ans, MOD - query(a[i].first, a[i].second, a[i].first, a[i].second));
F(j, i + 1, k) {
if (a[j].second == a[i].second) {
add(ans, query(a[i].first, a[i].second, a[j].first, a[j].second));
if (bg != 2e9) add(ans, MOD - query(a[i].first, a[i].second, a[j].first, bg));
if (sm != -2e9) add(ans, MOD - query(a[i].first, sm, a[j].first, a[j].second));
if (bg != 2e9 && sm != -2e9) add(ans, query(a[i].first, sm, a[j].first, bg));
break;
}
if (a[j].second > a[i].second) {
if (a[j].second < bg) {
// if (j < k && a[j + 1].first == a[j].first && a[j].second <= bg) bgok = false;
add(ans, query(a[i].first, a[i].second, a[j].first, a[j].second));
if (bg != 2e9) add(ans, MOD - query(a[i].first, a[i].second, a[j].first, bg));
if (sm != -2e9) add(ans, MOD - query(a[i].first, sm, a[j].first, a[j].second));
if (bg != 2e9 && sm != -2e9) add(ans, query(a[i].first, sm, a[j].first, bg));
bg = a[j].second;
}
} else {
if (j < k && a[j + 1].first == a[j].first && a[j + 1].second <= a[i].second) continue;
if (a[j].second > sm) {
// cout << "#> " << i << " " << j << " " << bgok << " " << smok << endl;
add(ans, query(a[i].first, a[j].second, a[j].first, a[i].second));
if (bg != 2e9) add(ans, MOD - query(a[i].first, a[j].second, a[j].first, bg));
if (sm != -2e9) add(ans, MOD - query(a[i].first, sm, a[j].first, a[i].second));
if (bg != 2e9 && sm != -2e9) add(ans, query(a[i].first, sm, a[j].first, bg));
sm = a[j].second;
}
}
}
}
cout << ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3420kb
input:
3 3 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3420kb
input:
5 5 2 2 1 2 4
output:
126
result:
ok 1 number(s): "126"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
6 6 5 4 1 3 2 2 4 1 5 5 3
output:
161
result:
ok 1 number(s): "161"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
15 38 6 12 6 7 15 2 18 3 19 4 2 14 29
output:
80066
result:
ok 1 number(s): "80066"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
5145 5419 9 547 285 294 284 375 385 217 857 348 925 14 274 3104 853 184 953 794 603
output:
334363567
result:
ok 1 number(s): "334363567"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
5 5 16 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4
output:
25
result:
ok 1 number(s): "25"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
9145 9419 12 123 456 223 456 547 285 294 284 375 385 217 857 348 925 14 274 1104 853 184 953 794 603 2234 5678
output:
921360185
result:
ok 1 number(s): "921360185"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
6 8 4 2 3 3 3 4 2 1 1
output:
444
result:
ok 1 number(s): "444"
Test #9:
score: 0
Accepted
time: 86ms
memory: 3472kb
input:
1000000000 1000000000 5000 1657 1 1644 1 1000000 116362 1186 1 2392 1 1560 1 995 1 2340 1 1916 1 2143 1 1762 1 1000000 116109 1651 1 1000000 116059 2289 1 1000000 115730 1000000 115896 1000000 116499 1608 1 342 1 1000000 116949 1965 1 1000000 114571 1000000 116602 2171 1 1000000 114848 1000000 11627...
output:
80025633
result:
ok 1 number(s): "80025633"
Test #10:
score: 0
Accepted
time: 91ms
memory: 3492kb
input:
1000000000 1000000000 5000 1 2581 1 2273 115983 1000000 116105 1000000 114552 1000000 1 1955 1 2254 116061 1000000 116182 1000000 115783 1000000 114564 1000000 116614 1000000 116229 1000000 116087 1000000 114956 1000000 1 2453 114766 1000000 115750 1000000 115448 1000000 1 1748 116665 1000000 1 2237...
output:
80025633
result:
ok 1 number(s): "80025633"
Test #11:
score: 0
Accepted
time: 115ms
memory: 3448kb
input:
1000000000 1000000000 5000 824 1 811 1 2300000 114696 353 1 1559 1 727 1 162 1 1507 1 1083 1 1310 1 929 1 1000000 116109 818 1 1000000 116059 1456 1 1000000 115730 1000000 115896 2300000 114833 775 1 2300000 115576 2300000 115283 1132 1 1000000 114571 2300000 114936 1338 1 1000000 114848 2300000 114...
output:
537083161
result:
ok 1 number(s): "537083161"
Test #12:
score: 0
Accepted
time: 116ms
memory: 3664kb
input:
1000000000 1000000000 5000 1 1748 1 1440 115983 1000000 116105 1000000 114552 1000000 1 1122 1 1421 116061 1000000 114516 2300000 115783 1000000 114564 1000000 114948 2300000 114563 2300000 116087 1000000 114956 1000000 1 1620 114766 1000000 115750 1000000 115448 1000000 1 915 114999 2300000 1 1404 ...
output:
537083161
result:
ok 1 number(s): "537083161"
Test #13:
score: 0
Accepted
time: 133ms
memory: 3452kb
input:
1000000000 1000000000 5000 2300000 115622 1000000 116216 1000000 116852 2300000 115827 2300000 116715 1000000 116212 2300000 116390 2300000 114646 1000000 114857 2300000 116404 1000000 116398 1000000 115409 2300000 115721 1000000 116136 2300000 114925 2300000 114869 2300000 116176 1000000 115774 100...
output:
129612365
result:
ok 1 number(s): "129612365"
Test #14:
score: 0
Accepted
time: 124ms
memory: 3428kb
input:
1000000000 1000000000 5000 116495 1000000 116269 1000000 115204 2300000 115724 1000000 116508 1000000 115095 2300000 116712 1000000 114789 2300000 115009 2300000 114795 1000000 115093 2300000 115612 1000000 116183 2300000 116140 2300000 116148 2300000 115608 2300000 115111 1000000 115058 1000000 115...
output:
129612365
result:
ok 1 number(s): "129612365"
Test #15:
score: 0
Accepted
time: 160ms
memory: 3472kb
input:
999999992 999999990 5000 1035170 5702575 3959104 3959104 3887901 7432303 11377527 9794948 6282049 47695 11781994 2037659 11292228 47695 6787467 878630 10441683 5492431 1240650 1129736 5631557 11377527 4863442 5631557 6662382 4863442 8837935 7070049 8837935 10441683 4878561 5702575 5610718 2664505 58...
output:
892807048
result:
ok 1 number(s): "892807048"
Test #16:
score: -100
Time Limit Exceeded
input:
999999948 999999898 5000 6033860 10854965 57219333 28077882 18498300 33290576 34559919 16960059 40765867 73389700 9985342 17984966 54717579 26853732 13059544 23513592 56562634 27758141 19776481 35613289 6632028 11929378 14942564 7329745 7337824 13208993 33584464 60460021 13330979 6539654 32561958 58...