QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127755#6736. Alice and BobOrmlis#AC ✓94ms81676kbC++202.4kb2023-07-20 01:06:142023-07-20 01:06:16

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-20 01:06:16]
  • 评测
  • 测评结果:AC
  • 用时:94ms
  • 内存:81676kb
  • [2023-07-20 01:06:14]
  • 提交

answer

#include "bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

int Bit(int mask, int b) { return (mask >> b) & 1; }

template<class T>
bool ckmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool ckmax(T &a, const T &b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

const int INFi = 2e9;
const ll INF = 1e18;
const int LG = 18;


constexpr int md = 998244353; //1e9 + 7, 1e9 + 9

inline int add(const int &a, const int &b) {
    return a + b >= md ? a + b - md : a + b;
}

inline int sub(const int &a, const int &b) {
    return a - b < 0 ? a - b + md : a - b;
}

inline int mul(const int &a, const int &b) {
    return (1ll * a * b) % md;
}


int pw(int a, ll b) {
    int res = 1;
    for(; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a);
    return res;
}

int rev(int a) {
    return pw(a, md - 2);
}



const int maxN = 1e7 + 5;
int fact[maxN];
int rfact[maxN];

using int128 = __int128;

void solve() {
    fact[0] = 1;
    for(int i = 1; i < maxN; ++i) fact[i] = (1ll * fact[i - 1] * i) % md;
    rfact[maxN - 1] = rev(fact[maxN - 1]);
    for (int i = maxN - 1; i >= 1; --i) rfact[i - 1] = (1ll * rfact[i] * i) % md;
    int n; cin >> n;
    __int128 ans = 0;
    int m = (n + 1) / 2;
    for(int x = 1; x <= m; ++x) ans += (__int128)fact[n - x] *  fact[n - x] * rfact[n - 2 * x + 1];
    ll answ = (ans % md);
    cout << answ << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(12) << fixed;
    int t = 1;
//    cin >> t;
    rep(i, t) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 77ms
memory: 81560kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 85ms
memory: 81560kb

input:

2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 88ms
memory: 81560kb

input:

10

output:

997920

result:

ok 1 number(s): "997920"

Test #4:

score: 0
Accepted
time: 76ms
memory: 81552kb

input:

100

output:

188898954

result:

ok 1 number(s): "188898954"

Test #5:

score: 0
Accepted
time: 80ms
memory: 81604kb

input:

4

output:

10

result:

ok 1 number(s): "10"

Test #6:

score: 0
Accepted
time: 76ms
memory: 81608kb

input:

8

output:

12336

result:

ok 1 number(s): "12336"

Test #7:

score: 0
Accepted
time: 88ms
memory: 81600kb

input:

16

output:

373118483

result:

ok 1 number(s): "373118483"

Test #8:

score: 0
Accepted
time: 77ms
memory: 81604kb

input:

32

output:

314585464

result:

ok 1 number(s): "314585464"

Test #9:

score: 0
Accepted
time: 85ms
memory: 81552kb

input:

64

output:

627827331

result:

ok 1 number(s): "627827331"

Test #10:

score: 0
Accepted
time: 80ms
memory: 81632kb

input:

128

output:

828497685

result:

ok 1 number(s): "828497685"

Test #11:

score: 0
Accepted
time: 92ms
memory: 81608kb

input:

256

output:

65697890

result:

ok 1 number(s): "65697890"

Test #12:

score: 0
Accepted
time: 73ms
memory: 81624kb

input:

512

output:

854187619

result:

ok 1 number(s): "854187619"

Test #13:

score: 0
Accepted
time: 76ms
memory: 81600kb

input:

1024

output:

513823539

result:

ok 1 number(s): "513823539"

Test #14:

score: 0
Accepted
time: 89ms
memory: 81676kb

input:

1361956

output:

617368199

result:

ok 1 number(s): "617368199"

Test #15:

score: 0
Accepted
time: 94ms
memory: 81664kb

input:

7579013

output:

827172636

result:

ok 1 number(s): "827172636"

Test #16:

score: 0
Accepted
time: 90ms
memory: 81576kb

input:

8145517

output:

710624331

result:

ok 1 number(s): "710624331"

Test #17:

score: 0
Accepted
time: 88ms
memory: 81596kb

input:

6140463

output:

707600568

result:

ok 1 number(s): "707600568"

Test #18:

score: 0
Accepted
time: 87ms
memory: 81556kb

input:

3515281

output:

698302413

result:

ok 1 number(s): "698302413"

Test #19:

score: 0
Accepted
time: 81ms
memory: 81592kb

input:

6969586

output:

69470392

result:

ok 1 number(s): "69470392"

Test #20:

score: 0
Accepted
time: 82ms
memory: 81604kb

input:

2888636

output:

433579983

result:

ok 1 number(s): "433579983"

Test #21:

score: 0
Accepted
time: 91ms
memory: 81596kb

input:

9999998

output:

758172780

result:

ok 1 number(s): "758172780"

Test #22:

score: 0
Accepted
time: 91ms
memory: 81596kb

input:

9999999

output:

605195495

result:

ok 1 number(s): "605195495"

Test #23:

score: 0
Accepted
time: 86ms
memory: 81568kb

input:

10000000

output:

866813682

result:

ok 1 number(s): "866813682"