QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#735284 | #4588. Feeder Robot | std_abs | AC ✓ | 14ms | 9540kb | C++20 | 3.7kb | 2024-11-11 18:57:03 | 2024-11-11 18:57:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) ((int)a.size())
const int mod = 998244353, N = 500005;
int add(int a, int b) {
a += b;
if (a >= mod) a -= mod;
return a;
}
int sub(int a, int b) {
a -= b;
if (a < 0) a += mod;
return a;
}
int mul(int a, int b) {
return 1ll * a * b % mod;
}
int Pow(int a, int b) {
int ans = 1;
for (; b; b >>= 1, a = mul(a, a)) {
if (b & 1) ans = mul(ans, a);
}
return ans;
}
int fac[N], ifac[N], inv[N];
int C(int n, int m) {
if (n < 0 || m < 0 || n < m) return 0;
return mul(fac[n], mul(ifac[m], ifac[n - m]));
}
int calc(int l, int r, int m) {
// x in [l, r], sum of C(x, m)
l = max(l, m);
if (l > r) return 0;
return sub(C(r + 1, m + 1), C(l, m + 1));
int ans = 0;
for (int i = l; i <= r; ++i) ans = add(ans, C(i, m));
return ans;
}
int calc2(int l, int r, int m) {
// x in [l, r], sum of x * C(x, m)
return sub(mul(add(m,1),calc(l+1,r+1,m+1)),calc(l,r,m));
int ans = 0;
for (int i = l; i <= r; ++i) ans = add(ans, mul(i, C(i, m)));
return ans;
}
int ifloor(int a, int b) {
if (a < 0 && a % b) return a / b - 1;
return a / b;
}
int solve(int n, int m, int s) {
int ans = 0;
for (int l = 1; l <= n; ++l) {
// t <= l + 1
// t = s + 2d + (m & 1)
// cout << "# " << n << ' ' << s << ' ' << (m & 1) << endl;
int lo = max(2 * l + s - m, 1), hi = min(s + l, n);
int cl = ifloor(lo - s - (m & 1), 2), cm = ifloor(min(l + 1, hi) - s - (m & 1), 2), cr = ifloor(hi - s - (m & 1), 2);
cl = max(cl, 0);
// cout << l << ' ' << cl << ' ' << cm << ' ' << cr << endl;
int off = (m + 1) / 2 - 1;
if (cl <= cm) {
int val = min(s + l, n) - (l + 1) + 1;
//cout << off << ' ' << val << endl;
ans = add(ans, mul(val, calc(off + cl, off + cm, l - 1)));
}
// cout << "$ " << l << " " << ans << endl;
cm = max(cm, cl-1);
// t > l + 1
if (cm + 1 <= cr) {
int val = min(s + l, n) - (s + (m & 1)) + 1;
// cout << val << endl;
ans = add(ans, mul(val, calc(off + cm + 1, off + cr, l - 1)));
// cout << "!!" << off + cm + 1 << ' ' << off + cr << ' ' << l - 1 << endl;
// cout << "$" << ans << endl;
int res = calc2(off + cm + 1, off + cr, l - 1);
res = sub(res, mul(calc(off + cm + 1, off + cr, l - 1), off));
// cout << "$" << res << endl;
// cout << "$# " << off << endl;
ans = sub(ans, mul(2, res));
}
// cout << l << ' ' << ans << endl;
}
return ans;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
inv[1] = fac[1] = ifac[1] = fac[0] = ifac[0] = 1;
for (int i = 2; i < N; ++i) {
inv[i] = sub(0, mul(inv[mod % i], mod / i));
fac[i] = mul(fac[i - 1], i);
ifac[i] = mul(ifac[i - 1], inv[i]);
}
int n, m, s;
cin >> n >> m >> s, --m;
if (m == 0) {
cout << "1\n";
return 0;
}
int ans = add(solve(n, m, s), solve(n, m, n + 1 - s));
for (int t = s; t <= s; ++t) {
if ((s - t - m) & 1) {
continue;
}
for (int l = abs(s - t); l <= (m + abs(s - t)) / 2 && l <= n; ++l) {
int a = min(min(s, t) + l, n) - max(max(s, t), l + 1) + 1;
int b = C((m + abs(s - t)) / 2 - 1, l - 1);
ans = sub(ans, mul(a, b));
}
}
cout << ans << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 9444kb
input:
4 3 2
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 5ms
memory: 9436kb
input:
3 5 2
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 3ms
memory: 9388kb
input:
3 6 2
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 6ms
memory: 9440kb
input:
2 1 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 9ms
memory: 9484kb
input:
93844 52779 41066
output:
15948404
result:
ok single line: '15948404'
Test #6:
score: 0
Accepted
time: 11ms
memory: 9388kb
input:
92974 83483 82913
output:
636534890
result:
ok single line: '636534890'
Test #7:
score: 0
Accepted
time: 12ms
memory: 9460kb
input:
99638 137843 27168
output:
140741998
result:
ok single line: '140741998'
Test #8:
score: 0
Accepted
time: 12ms
memory: 9448kb
input:
94776 189552 75037
output:
10943210
result:
ok single line: '10943210'
Test #9:
score: 0
Accepted
time: 10ms
memory: 9412kb
input:
98122 196243 51898
output:
433580635
result:
ok single line: '433580635'
Test #10:
score: 0
Accepted
time: 7ms
memory: 9460kb
input:
94799 16084 53852
output:
541300035
result:
ok single line: '541300035'
Test #11:
score: 0
Accepted
time: 3ms
memory: 9484kb
input:
99255 16270 82986
output:
632634215
result:
ok single line: '632634215'
Test #12:
score: 0
Accepted
time: 7ms
memory: 9540kb
input:
90711 30608 30607
output:
307199727
result:
ok single line: '307199727'
Test #13:
score: 0
Accepted
time: 5ms
memory: 9436kb
input:
90871 32515 58901
output:
399181127
result:
ok single line: '399181127'
Test #14:
score: 0
Accepted
time: 6ms
memory: 9444kb
input:
93683 78004 78004
output:
831042401
result:
ok single line: '831042401'
Test #15:
score: 0
Accepted
time: 7ms
memory: 9408kb
input:
100000 200000 1
output:
589878665
result:
ok single line: '589878665'
Test #16:
score: 0
Accepted
time: 10ms
memory: 9508kb
input:
99571 80584 77484
output:
76979677
result:
ok single line: '76979677'
Test #17:
score: 0
Accepted
time: 14ms
memory: 9452kb
input:
98701 195293 85881
output:
919188077
result:
ok single line: '919188077'
Test #18:
score: 0
Accepted
time: 12ms
memory: 9452kb
input:
94737 189474 75712
output:
982200756
result:
ok single line: '982200756'
Test #19:
score: 0
Accepted
time: 13ms
memory: 9468kb
input:
98009 196017 45230
output:
524502520
result:
ok single line: '524502520'
Test #20:
score: 0
Accepted
time: 8ms
memory: 9444kb
input:
52049 35335 40627
output:
392902294
result:
ok single line: '392902294'
Test #21:
score: 0
Accepted
time: 6ms
memory: 9484kb
input:
7886 20819 5683
output:
880753789
result:
ok single line: '880753789'
Test #22:
score: 0
Accepted
time: 3ms
memory: 9408kb
input:
12935 110431 1855
output:
486933187
result:
ok single line: '486933187'
Test #23:
score: 0
Accepted
time: 6ms
memory: 9412kb
input:
6998 185600 5309
output:
875572529
result:
ok single line: '875572529'
Test #24:
score: 0
Accepted
time: 6ms
memory: 9412kb
input:
263 21165 110
output:
313229096
result:
ok single line: '313229096'
Test #25:
score: 0
Accepted
time: 6ms
memory: 9408kb
input:
219 53168 41
output:
76548690
result:
ok single line: '76548690'
Test #26:
score: 0
Accepted
time: 8ms
memory: 9468kb
input:
99999 54881 99999
output:
925367915
result:
ok single line: '925367915'
Test #27:
score: 0
Accepted
time: 5ms
memory: 9396kb
input:
203 147828 93
output:
200963393
result:
ok single line: '200963393'
Test #28:
score: 0
Accepted
time: 0ms
memory: 9388kb
input:
53 115859 8
output:
879480153
result:
ok single line: '879480153'
Test #29:
score: 0
Accepted
time: 2ms
memory: 9392kb
input:
11 72161 7
output:
977588182
result:
ok single line: '977588182'
Test #30:
score: 0
Accepted
time: 0ms
memory: 9440kb
input:
7 137778 2
output:
411775054
result:
ok single line: '411775054'
Test #31:
score: 0
Accepted
time: 6ms
memory: 9464kb
input:
2 118098 2
output:
1
result:
ok single line: '1'
Test #32:
score: 0
Accepted
time: 10ms
memory: 9400kb
input:
68183 89994 24513
output:
222225778
result:
ok single line: '222225778'
Test #33:
score: 0
Accepted
time: 6ms
memory: 9444kb
input:
61307 87410 55321
output:
786087147
result:
ok single line: '786087147'
Test #34:
score: 0
Accepted
time: 7ms
memory: 9408kb
input:
69764 19857 4202
output:
378716277
result:
ok single line: '378716277'
Test #35:
score: 0
Accepted
time: 12ms
memory: 9448kb
input:
96982 133359 63344
output:
538396098
result:
ok single line: '538396098'
Test #36:
score: 0
Accepted
time: 7ms
memory: 9452kb
input:
67065 34184 14110
output:
215549451
result:
ok single line: '215549451'
Test #37:
score: 0
Accepted
time: 8ms
memory: 9448kb
input:
99999 99999 1
output:
849329297
result:
ok single line: '849329297'
Test #38:
score: 0
Accepted
time: 7ms
memory: 9488kb
input:
35816 25787 26887
output:
157398762
result:
ok single line: '157398762'
Test #39:
score: 0
Accepted
time: 10ms
memory: 9532kb
input:
100000 200000 50000
output:
126901190
result:
ok single line: '126901190'
Test #40:
score: 0
Accepted
time: 7ms
memory: 9408kb
input:
95928 23066 68608
output:
719104244
result:
ok single line: '719104244'
Test #41:
score: 0
Accepted
time: 6ms
memory: 9452kb
input:
96028 13641 82388
output:
546657868
result:
ok single line: '546657868'
Test #42:
score: 0
Accepted
time: 6ms
memory: 9412kb
input:
95448 14579 80871
output:
854157868
result:
ok single line: '854157868'
Test #43:
score: 0
Accepted
time: 8ms
memory: 9484kb
input:
94236 50517 58764
output:
337054003
result:
ok single line: '337054003'