提出 #75984630

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define endl '\n'
#define pb push_back
//#define int long long 
typedef long long ll;
typedef __int128 LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;

const int mod = 998244353;
ll qpow(ll a, ll b, int p)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}
ll inv[250005];
ll fact[250005];

int bi[250005], bl[1005], br[1005];
ll mul[1005], total[1005]; // 每个块内维护：mul每一项的阶乘之积；total维护每一项的总和
ll ans[250005];
int cnt[250005];

struct Query{
    int l, r, x, id;
}qry[250005];
bool cmp(Query a, Query b){
    if(bi[a.l] == bi[b.l]){
        if(bi[a.l] & 1) return a.r < b.r;
        else return a.r > b.r;
    }
    else{
        return bi[a.l] < bi[b.l];
    }
}

void del(int x){
    total[bi[x]] --;
    mul[bi[x]] = mul[bi[x]] * inv[cnt[x]] % mod;
    cnt[x] --;
}
void add(int x){
    cnt[x] ++;
    total[bi[x]] ++;
    mul[bi[x]] = mul[bi[x]] * cnt[x] % mod;
}

int n, q;
int a[250005];

void solve()
{
    cin >> n >> q;
    fact[0] = 1;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        inv[i] = qpow(i, mod - 2, mod);
        fact[i] = fact[i - 1] * i % mod;
    }
    const int blen = sqrt(n);
    const int bcnt = (n + blen - 1) / blen;
    for(int i = 1; i <= n; i ++){
        bi[i] = (i - 1) / blen + 1;
    }
    for(int i = 1; i <= bcnt; i ++){
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(n, i * blen);
        total[i] = 0;
        mul[i] = 1;
    }
    for(int i = 1; i <= q; i ++){
        int l, r, x;
        cin >> l >> r >> x;
        qry[i] = {l, r, x, i};
    }
    sort(qry + 1, qry + 1 + q, cmp);
    // cout << "OK\n";
    // return;
    int winl = 1, winr = 0;
    for(int i = 1; i <= q; i ++){
        auto [l, r, x, id] = qry[i];
        // cerr << l << " " << r << " " << x << " " << id << ":\n";
        while(winl > l) add(a[--winl]);
        while(winr < r) add(a[++winr]);
        while(winl < l) del(a[winl++]);
        while(winr > r) del(a[winr--]);
        if(x == 1) ans[id] = 1;
        else{
            int L = 1, R = x - 1;
            int tot = 0;
            ll m = 1;
            if(bi[L] == bi[R]){
                for(int i = L; i <= R; i ++){
                    tot += cnt[i];
                    m = (m * fact[cnt[i]]) % mod;
                }
            }
            else{
                for(int i = bi[L] + 1; i < bi[R]; i ++){
                    tot += total[i];
                    m = (m * mul[i]) % mod;
                }
                for(int i = L; i < bl[bi[L] + 1]; i ++){
                    tot += cnt[i];
                    m = (m * fact[cnt[i]]) % mod;
                }
                for(int i = br[bi[R] - 1] + 1; i <= R; i ++){
                    tot += cnt[i];
                    m = (m * fact[cnt[i]]) % mod;
                }
            }
            ans[id] = fact[tot] * qpow(m, mod - 2, mod) % mod;
        }
    }
    for(int i = 1; i <= q; i ++){
        cout << ans[i] << "\n";
    }
}


signed main()
{
//  freopen("in.txt", "rt", stdin);
//  freopen("out.txt", "wt", stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    // int T=1; cin>>T; while(T--)
    solve();
    return 0;
}

提出情報

ジャッジ結果