QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387201#6736. Alice and Bobk1nsomTL 0ms0kbC++171.1kb2024-04-12 09:15:292024-04-12 09:15:29

Judging History

This is the latest submission verdict.

  • [2024-04-12 09:15:29]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2024-04-12 09:15:29]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 10000005
#define endl '\n'
#define mod 998244353
int n, ans, col, jc[N + 5] = {0}, inv[N + 5] = {0};
int kpow(int x, int k)
{
    int n = x, ret = 1;
    while (k)
    {
        if (k & 1)
            ret = (ret * n) % mod;
        n = (n * n) % mod;
        k >>= 1;
    }
    return ret;
}
void init()
{
    jc[0] = 1;
    for (int i = 1; i <= N; i++)
        jc[i] = (i * jc[i - 1]) % mod;
    inv[1] = 1;
    inv[0] = 0;
    for (int i = 2; i <= N; i++)
        inv[i] = kpow(jc[i], mod - 2);
}
signed main()
{
    cin >> n;
    col = 1;
    init();
    for (int i = 1; 2 * i <= n + 1; i++)
    {
        // cout << n - i << ' ' << n - 2 * i + 1 << ' ' << i - 1 << endl;
        if (i - 1 == 0 || n + 1 == 2 * i)
            ans = (ans + jc[i - 1] * jc[n - i] % mod) % mod;
        else
            ans = (ans + jc[n - i] * inv[n - 2 * i + 1] % mod * inv[i - 1] % mod * jc[i - 1] % mod * jc[n - i] % mod) % mod; // col(n - i, i - 1)
    }
    cout << ans << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

1

output:

1

result: