QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#475507#6736. Alice and Bobyudiao_vickyWA 0ms3544kbC++111.2kb2024-07-13 15:08:152024-07-13 15:08:15

Judging History

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

  • [2024-07-13 15:08:15]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3544kb
  • [2024-07-13 15:08:15]
  • 提交

answer

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

// 用于快速幂的函数
ll qpow(ll a, ll b, ll mod) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

void solve() {
    int n;
    cin >> n;
    if (n == 1 || n == 2) {
        cout << 0 << endl;
        return;
    }
    
    // 计算阶乘和逆元
    vector<ll> fac(n + 1), ifac(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    ifac[n] = qpow(fac[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; --i) {
        ifac[i] = ifac[i + 1] * (i + 1) % MOD;
    }
    
    // 计算答案
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (i % 2 == 1) {
            ans = (ans + fac[n] * ifac[i] % MOD * ifac[n - i] % MOD) % MOD;
        } else {
            ans = (ans - fac[n] * ifac[i] % MOD * ifac[n - i] % MOD + MOD) % MOD;
        }
    }
    
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3544kb

input:

1

output:

0

result:

wrong answer 1st numbers differ - expected: '1', found: '0'