QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#125293#6736. Alice and BobrniyaAC ✓185ms81252kbC++171.7kb2023-07-16 14:58:492023-07-16 14:58:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-16 14:58:50]
  • 评测
  • 测评结果:AC
  • 用时:185ms
  • 内存:81252kb
  • [2023-07-16 14:58:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

constexpr long long mod = 998244353;

struct mint {
    long long x;
    mint(long long xx = 0) : x((xx % mod + mod) % mod) {}
    mint& operator+=(mint r) {
        x += r.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(mint r) {
        if (x < r.x) x += mod;
        x %= mod;
        return *this;
    }
    mint& operator*=(mint r) {
        x *= r.x;
        x %= mod;
        return *this;
    }
    mint& operator/=(mint r) {
        x *= r.inv().x;
        x %= mod;
        return *this;
    };
    mint pow(long long n) {
        assert(0 <= n);
        mint a = *this, r = 1;
        while (n) {
            if (n & 1) r *= a;
            a *= a;
            n >>= 1;
        }
        return r;
    }
    mint inv() { return pow(mod - 2); }

    friend mint operator+(mint l, mint r) { return mint(l) += r; }
    friend mint operator-(mint l, mint r) { return mint(l) -= r; }
    friend mint operator*(mint l, mint r) { return mint(l) *= r; }
    friend mint operator/(mint l, mint r) { return mint(l) /= r; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;

    mint ans = 0;
    vector<mint> invs(n + 1);
    invs[0] = mint(0);
    invs[1] = mint(1);
    for (int i = 2; i <= n; i++) invs[i] = -1 * invs[mod % i] * (mod / i);
    mint fac = 1, finv = 1;
    for (int i = 1; i < n; i++) {
        fac *= i;
        finv *= invs[i];
    }
    for (int i = 1; n - 2 * i + 1 >= 0 and i <= n; i++) {
        ans += fac * fac * finv;
        fac *= invs[n - i];
        finv *= n - 2 * i + 1;
        finv *= n - 2 * i;
    }

    cout << ans.x << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3392kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3424kb

input:

2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3436kb

input:

10

output:

997920

result:

ok 1 number(s): "997920"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3392kb

input:

100

output:

188898954

result:

ok 1 number(s): "188898954"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

4

output:

10

result:

ok 1 number(s): "10"

Test #6:

score: 0
Accepted
time: 1ms
memory: 3436kb

input:

8

output:

12336

result:

ok 1 number(s): "12336"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

16

output:

373118483

result:

ok 1 number(s): "373118483"

Test #8:

score: 0
Accepted
time: 1ms
memory: 3400kb

input:

32

output:

314585464

result:

ok 1 number(s): "314585464"

Test #9:

score: 0
Accepted
time: 1ms
memory: 3496kb

input:

64

output:

627827331

result:

ok 1 number(s): "627827331"

Test #10:

score: 0
Accepted
time: 1ms
memory: 3460kb

input:

128

output:

828497685

result:

ok 1 number(s): "828497685"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3400kb

input:

256

output:

65697890

result:

ok 1 number(s): "65697890"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3440kb

input:

512

output:

854187619

result:

ok 1 number(s): "854187619"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3424kb

input:

1024

output:

513823539

result:

ok 1 number(s): "513823539"

Test #14:

score: 0
Accepted
time: 20ms
memory: 13820kb

input:

1361956

output:

617368199

result:

ok 1 number(s): "617368199"

Test #15:

score: 0
Accepted
time: 128ms
memory: 62144kb

input:

7579013

output:

827172636

result:

ok 1 number(s): "827172636"

Test #16:

score: 0
Accepted
time: 137ms
memory: 66664kb

input:

8145517

output:

710624331

result:

ok 1 number(s): "710624331"

Test #17:

score: 0
Accepted
time: 102ms
memory: 51088kb

input:

6140463

output:

707600568

result:

ok 1 number(s): "707600568"

Test #18:

score: 0
Accepted
time: 52ms
memory: 30420kb

input:

3515281

output:

698302413

result:

ok 1 number(s): "698302413"

Test #19:

score: 0
Accepted
time: 110ms
memory: 57540kb

input:

6969586

output:

69470392

result:

ok 1 number(s): "69470392"

Test #20:

score: 0
Accepted
time: 44ms
memory: 25512kb

input:

2888636

output:

433579983

result:

ok 1 number(s): "433579983"

Test #21:

score: 0
Accepted
time: 185ms
memory: 81216kb

input:

9999998

output:

758172780

result:

ok 1 number(s): "758172780"

Test #22:

score: 0
Accepted
time: 174ms
memory: 81236kb

input:

9999999

output:

605195495

result:

ok 1 number(s): "605195495"

Test #23:

score: 0
Accepted
time: 172ms
memory: 81252kb

input:

10000000

output:

866813682

result:

ok 1 number(s): "866813682"