#934868 (C++17) No.2568 列辞書順列列

• 問題: No.2568 列辞書順列列
• ユーザー: yasunori
• 提出日時: 2023-12-02 16:00:03
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 462 ms / 3,000 ms
• コード長: 5,249 bytes
• コンパイル時間: 2,368 ms
• コンパイル使用メモリ: 213,016 KB
• 実行使用メモリ: 7,348 KB
• 最終ジャッジ日時: 2023-12-02 16:00:20
• 合計ジャッジ時間: 14,801 ms
• ジャッジサーバーID （参考情報）: judge13 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,676 KB
testcase_01	AC	2 ms; 6,676 KB
testcase_02	AC	170 ms; 6,676 KB
testcase_03	AC	169 ms; 6,676 KB
testcase_04	AC	370 ms; 7,348 KB
testcase_05	AC	352 ms; 7,348 KB
testcase_06	AC	347 ms; 7,348 KB
testcase_07	AC	348 ms; 7,348 KB
testcase_08	AC	348 ms; 7,348 KB
testcase_09	AC	393 ms; 7,348 KB
testcase_10	AC	395 ms; 7,348 KB
testcase_11	AC	407 ms; 7,348 KB
testcase_12	AC	445 ms; 7,348 KB
testcase_13	AC	462 ms; 7,348 KB
testcase_14	AC	443 ms; 7,348 KB
testcase_15	AC	440 ms; 7,348 KB
testcase_16	AC	442 ms; 7,348 KB
testcase_17	AC	411 ms; 7,348 KB
testcase_18	AC	383 ms; 7,348 KB
testcase_19	AC	385 ms; 7,348 KB
testcase_20	AC	394 ms; 7,348 KB
testcase_21	AC	386 ms; 7,348 KB
testcase_22	AC	383 ms; 7,348 KB
testcase_23	AC	387 ms; 7,348 KB
testcase_24	AC	382 ms; 7,348 KB
testcase_25	AC	383 ms; 7,348 KB
testcase_26	AC	384 ms; 7,348 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;
template <typename T> using min_priority_queue = priority_queue<T,vector<T>,greater<T>>;

template<typename T>
void printv(vector<T> &v){
    bool b = false;
    for(auto i : v){
        if(b) cout << " ";
        else b = true;
        cout << i;
    }
    cout << endl;
}

template <typename T>
bool chmin(T &a, const T& b) {
    if (a > b) {
        a = b;  // aをbで更新
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T &a, const T& b) {
    if (a < b) {
        a = b;  // aをbで更新
        return true;
    }
    return false;
}

template <typename T>
T exEuclid(T a, T b, T &x, T &y){
    T d = a;
    if(b != 0){
        d = exEuclid(b, a%b, y, x);
        y -= (a/b)*x;
    }
    else{
        x = 1;
        y = 0;
    }
    //cout << a << " * " << x << " + " << b << " * " << y << " = " << d << endl;
    return d;
}

int64_t mod;
struct modint{
    int64_t n;
    int64_t p;

    modint(){
        n = 0;
        p = mod;
    }
    modint(int64_t a){
        if(a <= -mod) a %= mod;
        else if(a >= mod) a %= mod;
        if(a < 0) a += mod;
        n = a;
        p = mod;
    }
    modint(int64_t a, int64_t q){
        if(a <= -q) a %= q;
        else if(a >= q) a %= q;
        if(a < 0) a += q;
        n = a;
        p = q;
    }

    modint pow(int64_t a){
        if(a <= 1-p) a %= p-1;
        else if(a >= p-1) a %= p-1;
        if(a < 0) a += p-1;

        modint rtn;
        if(n == 0) {
            rtn.n = 0;
            return rtn;
        }
        if(n == 1) {
            rtn.n = 1;
            return rtn;
        }
        if(a == 0) {
            rtn.n = 1;
            return rtn;
        }
        if(a == 1) {
            rtn.n = n;
            return rtn;
        }

        int64_t b = a/2;
        int64_t c = a%2;
        rtn = pow(b);
        rtn *= rtn;
        if(c){
            rtn *= modint(n);
        }
        return rtn;
    }

    modint operator+(modint other){
        modint rtn(n+other.n, p);
        return rtn;
    }
    modint operator-(modint other){
        modint rtn(n-other.n, p);
        return rtn;
    }
    modint operator*(modint other){
        modint rtn(n*other.n, p);
        return rtn;
    }
    modint operator/(modint other){
        int64_t x, y, d;
        d = exEuclid(other.n, p, x, y);
        int64_t rtn = x*n;
        if(d > 1) rtn /= d;
        return modint(rtn);
    }

    void operator+=(modint other){
        n += other.n;
        if(n >= p) n %= p;
    }
    void operator-=(modint other){
        n -= other.n;
        if(n < 0) n += p;
    }
    void operator*=(modint other){
        n *= other.n;
        if(n >= p) n %= p;
    }
    void operator/=(modint other){
        int64_t x, y, d;
        d = exEuclid(other.n, p, x, y);
        n *= x;
        if(d > 1) n /= d;
        if(n <= p || p <= n) n %= p;
        if(n < 0) n += p;
        return;
    }
    void operator++(){
        n++;
        if(n == p) n = 0;
        return;
    }
    void operator--(){
        n--;
        if(n == -1) n = p-1;
        return;
    }
};

vector<modint> fact_mod_v;
vector<modint> inv_fact_mod_v;

modint comb_mod(int64_t n, int64_t m){
    if(n < 0 || m < 0 || m > n) return 0;
    modint rtn = fact_mod_v[n]*inv_fact_mod_v[m]*inv_fact_mod_v[n-m];
    return rtn;
}

modint comb_mod_small(int64_t n, int64_t m){
    if(m < mod){
        return comb_mod(n%mod, m);
    }
    return comb_mod_small(n/mod, m/mod)*comb_mod(n%mod, m%mod);
}

void init_fact(int64_t n){
    fact_mod_v.resize(n+1,0);
    inv_fact_mod_v.resize(n+1,0);
    for(int64_t i = 0; i <= n; i++){
        if(i == 0){
            fact_mod_v[i] = modint(1);
        }
        else{
            fact_mod_v[i] = modint(i*fact_mod_v[i-1].n);
        }
        //cout << i << endl;
    }
    for(int64_t i = min(n, mod-1); i >= 0; i--){
        if(i == min(n, mod-1)){
            inv_fact_mod_v[i] = modint(fact_mod_v[i]).pow(-1);
        }
        else{
            inv_fact_mod_v[i] = modint(inv_fact_mod_v[i+1].n*(i+1));
        }
        //cout << i << endl;
    }
}

void yn(bool b){
    if(b) cout << "Yes" << endl;
    else cout << "No" << endl;
}

bool debug;
bool randomInput;
void input(){
    if(debug && randomInput){
        
    }
    else{
        
    }
    return;
}

void calc(){
    mod = 998244353;
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> A(N);
    for(int i = 0; i < N; i++){
        cin >> A[i];
        A[i]--;
    }

    vector<modint> V(N+1, 0);
    for(int i = N-1; i >= 0; i--){
        V[i] = V[i+1] + modint(A[i]) * modint(M).pow(N-1-i);
    }


    for(int i = 0; i < Q; i++){
        int l, r;
        cin >> l >> r;
        l--; r--;

        modint ans = (V[l] - V[r+1]) / modint(M).pow(N-r-1) + 1;
        cout << ans.n << endl;
    }
    return;
}

int64_t ansSimple;
void calcSimple(){
    return;
}

void calc1(){
    int t; cin >> t;
    for(int i = 0; i < t; i++){
        input();
        calc();
        calcSimple();
    }
}

int main(){
    debug = 0;
    randomInput = 0;
    srand(time(NULL));
    cout << fixed << setprecision(12);
    if(debug){
        calc1();
    }
    else{
        input();
        calc();
    }
    return 0;
}
//