compro-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ningenMe/compro-library

:heavy_check_mark: test/util/ModInt.test.cpp

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/1067"

#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
#include "../../lib/00-util/ModInt.cpp"

constexpr long long MOD2 = 998244353;
using modint = ModInt<MOD2>;
int main() {
    long long N,Q; cin >> N >> Q;
    vector<long long> A(N+1,1234567890LL);
    for(int i = 1; i <= N; ++i) cin >> A[i];
	sort(A.begin(),A.end(),greater<>());
    A.push_back(0);
    vector<long long> L(Q),R(Q),P(Q);
    for(int i = 0; i < Q; ++i) cin >> L[i] >> R[i] >> P[i];
    priority_queue<pair<long long,int>> pq;
    for(int i = 0; i < Q; ++i) {
        for(int j = L[i]; j <= R[i]; ++j) {
            pq.push({j,P[i]});
        }
    }
    vector<vector<modint>> dp(2,vector<modint>(N+2));
    dp[0][0]=1;
    modint cnt = 1;
    for(int i = 1; i <= N; ++i) cnt *= A[i];
    map<pair<long long,int>,modint> mp;
    for(int i = 1; i <= N+1; ++i) {
        while(pq.size() && pq.top().first>A[i]) {
            auto p = pq.top();
            pq.pop();
            mp[p]=dp[(i-1)%2][p.second]*cnt;
        }
        for(int j = 0; j <= N; ++j) {
            dp[i%2][j] = 0;
        }
        for(int j = 0; j <= i-1; ++j) {
            dp[i%2][j+1] += dp[(i-1)%2][j];
            dp[i%2][j]   += dp[(i-1)%2][j]*(A[i]-1);
        }
        cnt /= A[i];
    }
    for(int i = 0; i < Q; ++i) {
        modint ans = 0;
        for(int j = L[i]; j <= R[i]; ++j) {
            ans ^= mp[{j,P[i]}];
        }
        cout << ans << endl;
    }
    return 0;
}
#line 1 "test/util/ModInt.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1067"

#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
#line 1 "lib/00-util/ModInt.cpp"
/*
 * @title ModInt
 * @docs md/util/ModInt.md
 */
template<long long mod> class ModInt {
public:
    long long x;
    constexpr ModInt():x(0) {}
    constexpr ModInt(long long y) : x(y>=0?(y%mod): (mod - (-y)%mod)%mod) {}
    constexpr ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}
    constexpr ModInt &operator+=(const long long y) {ModInt p(y);if((x += p.x) >= mod) x -= mod;return *this;}
    constexpr ModInt &operator+=(const int y) {ModInt p(y);if((x += p.x) >= mod) x -= mod;return *this;}
    constexpr ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}
    constexpr ModInt &operator-=(const long long y) {ModInt p(y);if((x += mod - p.x) >= mod) x -= mod;return *this;}
    constexpr ModInt &operator-=(const int y) {ModInt p(y);if((x += mod - p.x) >= mod) x -= mod;return *this;}
    constexpr ModInt &operator*=(const ModInt &p) {x = (x * p.x % mod);return *this;}
    constexpr ModInt &operator*=(const long long y) {ModInt p(y);x = (x * p.x % mod);return *this;}
    constexpr ModInt &operator*=(const int y) {ModInt p(y);x = (x * p.x % mod);return *this;}
    constexpr ModInt &operator^=(const ModInt &p) {x = (x ^ p.x) % mod;return *this;}
    constexpr ModInt &operator^=(const long long y) {ModInt p(y);x = (x ^ p.x) % mod;return *this;}
    constexpr ModInt &operator^=(const int y) {ModInt p(y);x = (x ^ p.x) % mod;return *this;}
    constexpr ModInt &operator/=(const ModInt &p) {*this *= p.inv();return *this;}
    constexpr ModInt &operator/=(const long long y) {ModInt p(y);*this *= p.inv();return *this;}
    constexpr ModInt &operator/=(const int y) {ModInt p(y);*this *= p.inv();return *this;}
    constexpr ModInt operator=(const int y) {ModInt p(y);*this = p;return *this;}
    constexpr ModInt operator=(const long long y) {ModInt p(y);*this = p;return *this;}
    constexpr ModInt operator-() const {return ModInt(-x); }
    constexpr ModInt operator++() {x++;if(x>=mod) x-=mod;return *this;}
    constexpr ModInt operator--() {x--;if(x<0) x+=mod;return *this;}
    constexpr ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    constexpr ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    constexpr ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    constexpr ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    constexpr ModInt operator^(const ModInt &p) const { return ModInt(*this) ^= p; }
    constexpr bool operator==(const ModInt &p) const { return x == p.x; }
    constexpr bool operator!=(const ModInt &p) const { return x != p.x; }
    // ModInt inv() const {int a=x,b=mod,u=1,v=0,t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);} return ModInt(u);}
    constexpr ModInt inv() const {int a=x,b=mod,u=1,v=0,t=0,tmp=0;while(b > 0) {t = a / b;a-=t*b;tmp=a;a=b;b=tmp;u-=t*v;tmp=u;u=v;v=tmp;} return ModInt(u);}
    constexpr ModInt pow(long long n) const {ModInt ret(1), mul(x);for(;n > 0;mul *= mul,n >>= 1) if(n & 1) ret *= mul;return ret;}
    friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;}
    friend istream &operator>>(istream &is, ModInt &a) {long long t;is >> t;a = ModInt<mod>(t);return (is);}
};
constexpr long long MOD_998244353 = 998244353;
constexpr long long MOD_1000000007 = 1'000'000'000LL + 7; //'
#line 10 "test/util/ModInt.test.cpp"

constexpr long long MOD2 = 998244353;
using modint = ModInt<MOD2>;
int main() {
    long long N,Q; cin >> N >> Q;
    vector<long long> A(N+1,1234567890LL);
    for(int i = 1; i <= N; ++i) cin >> A[i];
	sort(A.begin(),A.end(),greater<>());
    A.push_back(0);
    vector<long long> L(Q),R(Q),P(Q);
    for(int i = 0; i < Q; ++i) cin >> L[i] >> R[i] >> P[i];
    priority_queue<pair<long long,int>> pq;
    for(int i = 0; i < Q; ++i) {
        for(int j = L[i]; j <= R[i]; ++j) {
            pq.push({j,P[i]});
        }
    }
    vector<vector<modint>> dp(2,vector<modint>(N+2));
    dp[0][0]=1;
    modint cnt = 1;
    for(int i = 1; i <= N; ++i) cnt *= A[i];
    map<pair<long long,int>,modint> mp;
    for(int i = 1; i <= N+1; ++i) {
        while(pq.size() && pq.top().first>A[i]) {
            auto p = pq.top();
            pq.pop();
            mp[p]=dp[(i-1)%2][p.second]*cnt;
        }
        for(int j = 0; j <= N; ++j) {
            dp[i%2][j] = 0;
        }
        for(int j = 0; j <= i-1; ++j) {
            dp[i%2][j+1] += dp[(i-1)%2][j];
            dp[i%2][j]   += dp[(i-1)%2][j]*(A[i]-1);
        }
        cnt /= A[i];
    }
    for(int i = 0; i < Q; ++i) {
        modint ans = 0;
        for(int j = L[i]; j <= R[i]; ++j) {
            ans ^= mp[{j,P[i]}];
        }
        cout << ans << endl;
    }
    return 0;
}
Back to top page