提出 #74883713

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
ll modmul(ll a, ll b, ll m) { return (ll)((__int128)a*b % m); }
ll modpow(ll b, ll e, ll m) {
    ll ans = 1;
    for (; e; b = modmul(b, b, m), e /= 2)
    if (e & 1) ans = modmul(ans, b, m);
    return ans;
}
const int M = 998244353, MAXN = 200000;
ll fac[MAXN+5], finv[MAXN+5];
void init() {
    fac[0] = 1;
    for (int i = 1; i <= MAXN; i++)
    fac[i] = modmul(fac[i-1], i, M);
    finv[MAXN] = modpow(fac[MAXN], M-2, M);
    for (int i = MAXN-1; i >= 0; i--)
    finv[i] = modmul(finv[i+1], i+1, M);
}
ll nCk(int n, int k) {
    if (n < k || k < 0) return 0;
    ll r = modmul(fac[n], finv[n-k], M);
    return modmul(r, finv[k], M);
}
int main() {
    fastio; int N; cin >> N;
    vector<int> v(N+1), v2(v);
    for (int i = 0; i < N; i++) {
        int a, b; cin >> a >> b;
        v[a]++; v[b+1]--;
        if (max(a, N-b) <= min(b, N-a)) v2[max(a, N-b)]++, v2[min(b, N-a)+1]--;
    }
    for (int i = 1; i <= N; i++) {
        v[i] += v[i-1];
        v2[i] += v2[i-1];
    }
    init();
    ll ans = 0;
    for (int i = 1; i < N; i++) {
        int a = v[i], b = v[N-i], ab = v2[i];
        if (a+b-N != ab) continue;
        ans = (ans + nCk(ab, i-(a-ab))) % M;
    }
    cout << ans << "\n";
    return 0;
}

提出情報

ジャッジ結果