結果

問題 No.2568 列辞書順列列
ユーザー uetaueta
提出日時 2023-12-02 16:59:55
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 11,186 bytes
コンパイル時間 4,126 ms
コンパイル使用メモリ 164,836 KB
実行使用メモリ 14,448 KB
最終ジャッジ日時 2024-09-26 21:00:14
合計ジャッジ時間 11,041 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <cstdint>
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define fore(i, a) for(auto &&i : a)
#define foreP(a, b, v) for(auto &&[a, b] : v)
#define foreP3(a, b, c, v) for(auto &&[a, b, c] : v)
#define fitr(itr, m) for(auto &&itr=m.begin();itr!=m.end();itr++)
#define ALL(v) (v).begin(),(v).end()
#define SUM(a) accumulate(ALL(a),0LL)
#define VC vector
#define TP tuple

using namespace std;
mt19937 engine(time(0));

using ll = long long;
using ld = long double;
constexpr long long mod = 998244353;
// constexpr long long mod = 1000000007;
// constexpr long long mod = 100000000000000003;
constexpr double PI=3.1415926535897932384626433832795028841971;
constexpr long long inf = INT_MAX;
constexpr long long infll = LONG_MAX;

int dx[8] = {1, 0,-1, 0, 1, 1,-1,-1};
int dy[8] = {0, 1, 0,-1, 1,-1, 1,-1 };

using Si =set<int>;using Sll =set<long long>;using Sc =set<char>;using Ss =set<string>;
using Mii = map<int,int>;using Msi = map<string,int>;using Mci = map<char,int>;using Mlli = map<long long,int>;
using P = pair<int, int>;using PL = pair<long long, long long>;
using V = vector<int>;using VL = vector<long long>;using Vc = vector<char>;using Vs = vector<string>;
using VP = vector<P>;using VPL = vector<P>;
using VV = vector<vector<int>>;using VVL = vector<vector<long long>>;
using VVc = vector<vector<char>>;using VVs = vector<vector<string>>;
using VVP = vector<vector<P>>;using VVPL = vector<vector<PL>>;
using VVV = vector<vector<vector<int>>>;using VVVL = vector<vector<vector<ll>>>;using VVVP = vector<vector<vector<P>>>;

template<class T,class S>bool chmin(T& a, S b) {if(a<=b)return false;a = b;return true;};
template<class T,class S>bool chmax(T& a, S b) {if(a>=b)return false;a = b;return true;};

ll modpow(ll x, ll n, ll m = mod) {
    if (n < 0) {ll res = modpow(x, -n, m);return modpow(res, m - 2, m);}
	if (abs(x) >= m)x %= m;if (x < 0)x += m;//if (x == 0)return 0;
	ll res = 1;
	while (n) {if (n & 1)res = res * x % m;x = x * x % m; n >>= 1;}
	return res;
}

class modint {
public:
    int val;
    modint() :val(0) {}
    template<typename T>modint(T x=0): val(x%mod){if(val<0)val+=mod;}
    modint(const modint &r){val=r.val;}
    modint& operator=(const modint& other) {val = other.val;return *this;}
    modint& operator=(const int& other) {val = other;return *this;}
    modint& operator=(const long long& other) {val = other;return *this;}
    //算術演算子
    modint operator +(){return (*this);} //単項
    modint operator -(){return (val%mod+mod)%mod;} //単項
    modint operator +(const modint &r){return modint(*this)+=r;}
    modint operator -(const modint &r){return modint(*this)-=r;}
    modint operator *(const modint &r){return modint(*this)*=r;}
    modint operator /(const modint &r){return modint(*this)/=r;}
    modint operator %(const modint &r){return modint(*this)%=r;}
    modint operator ^(long long r){modint ans = 1, x = val;while (r > 0) {if (r & 1) ans *= x;x *= x;r >>= 1;}return ans;}
    modint operator ++(int){val+=1;val%=mod; return *this;}
    modint operator --(int){(val==0)?val=mod-1:val-=1; return *this;}
    //代入演算子
    modint &operator +=(const modint &r){val+=r.val;if(val>=mod)val-=mod;return *this;}
    modint &operator -=(const modint &r){if(val<r.val)val+=mod;val-=r.val;return *this;}
    modint &operator *=(const modint &r){val=(ll)val*r.val%mod;return *this;}
    modint &operator /=(const modint &r){ll a=r.val,b=mod,u=1,v=0;while(b){ll t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}val=val*u%mod;if(val<0)val+=mod;return *this;}
    modint &operator %=(const modint &r){val=val%r.val; return *this;}
    modint &operator ^=(const long long &r){(*this)=(*this)^r; return (*this);}
    //等価比較演算子
    bool operator ==(const modint& r){return this->val==r.val;}
    bool operator <(const modint& r){return this->val<r.val;}
    bool operator >(const modint& r){return this->val>r.val;}
    bool operator !=(const modint& r){return this->val!=r.val;}
    // 他のクラスとの計算
    template <typename T>friend modint operator+(T t, const modint& o) {return modint(t) + o;}
    template <typename T>friend modint operator-(T t, const modint& o) {return modint(t) - o;}
    template <typename T>friend modint operator*(T t, const modint& o) {return modint(t) * o;}
    template <typename T>friend modint operator/(T t, const modint& o) {return modint(t) / o;}
};
istream &operator >>(istream &is,modint& x){ long long t; is >> t; x=modint(t); return is;}
ostream &operator <<(ostream &os,const modint& x){return os<<x.val;}

const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = (1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * (i + 1);
	}
	factinv[max_n - 1] = (1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] *(i + 1);
	}
}

modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[a - b];
}

template<typename T>
T gcd(T a, T b) {
	a = abs(a); b = abs(b);
	if (a < b)swap(a, b);
	while(b){ll r = a % b; a = b; b = r;}
	return a;
}

template <class T,class S> istream &operator>>(istream &is, pair<T,S> &pir) {is >> pir.first >> pir.second; return is;}
template <class T> istream &operator>>(istream &is, vector<T> &vec) {for(T &i: vec) is >> i; return is;}
template <class... T> istream &operator>>(istream &is, tuple<T...> &tpl) {apply([&is](auto &&...args) { ((is >> args), ...); }, tpl);return is;}

template <class OStream, class T> OStream &operator<<(OStream &os, const vector<T> &vec) {auto itr = vec.begin();while (itr != vec.end()){os << *itr; itr++;if(itr!=vec.end())os <<" ";}return os;}
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const array<T, sz> &arr) {auto itr = arr.begin();while (itr != arr.end()){os << *itr; itr++;if(itr!=arr.end())os <<" ";}return os;}
template <class OStream, class... T> OStream &operator<<(OStream &os, const tuple<T...> &tpl) {apply([&os](auto &&...args) {int count = 0;((os << args << (++count != sizeof...(args) ? " " : "")), ...);}, tpl);return os;}
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa) {return os  << pa.first << ' ' << pa.second;}
template <class OStream, class T> OStream &operator<<(OStream &os, const set<T> &vec) {auto itr = vec.begin();while (itr != vec.end()){os << *itr; itr++;if(itr!=vec.end())os <<" ";}return os;}

template <class OStream, class T> OStream &operator<<(OStream &os, const deque<T> &vec) {os << "deq[";for (auto v : vec) os << v << ',';os << ']';return os;}
template <class OStream, class T> OStream &operator<<(OStream &os, const queue<T> &vec) {os << "que[";for (auto v : vec) os << v << ',';os << ']';return os;}
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const map<TK, TV> &mp) {os << '{';for (auto v : mp) os << v.first << "=>" << v.second << ','<< endl;os << '}';return os;}
template<typename T>void out(T a){ cout << a << endl;}
template<typename T,typename S>void out(T a,S b){ cout << a <<" " << b << endl;}
template<typename T,typename S,typename U>void out(T a,S b,U c){ cout << a <<" " << b <<" " << c << endl;}
void yes(bool f=1,string yes="Yes",string no="No"){if(f){cout << yes << endl;}else{cout << no << endl;}}


//https://github.com/atcoder/ac-library
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
    int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }

    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size, r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n); assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

private:
    int _n, size, log;
    std::vector<S> d;
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

using S = modint;
S op(S a, S b) { return a + b; }
S e() { return modint(0); }

void solve(){
    int N,M,Q;
    cin >> N >> M >> Q;
    if(M==1){
        while (Q--)
            cout << 0 << endl;
        return;
    }
    VC<modint> A(N);
    cin >> A;
    rep(i,N){
        A[i] = (A[i]-1) * modint(M)^(N-i);
    }
    segtree<modint, op, e> seg(A);
    
    while(Q--){
        int l, r;
        cin >> l >> r;
        l--;
        modint ans = seg.prod(l, r);
        ans /= modint(M) ^ (N - r + 1);
        cout <<"ans" <<  ans + modint(1) << endl;
    }
    return;
}

int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<setprecision(20);
    int t=1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}
0