QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735284#4588. Feeder Robotstd_absAC ✓14ms9540kbC++203.7kb2024-11-11 18:57:032024-11-11 18:57:03

Judging History

This is the latest submission verdict.

  • [2024-11-11 18:57:03]
  • Judged
  • Verdict: AC
  • Time: 14ms
  • Memory: 9540kb
  • [2024-11-11 18:57:03]
  • Submitted

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'