結果
問題 | No.2571 列辞書順列 |
ユーザー |
![]() |
提出日時 | 2023-12-06 01:52:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,027 bytes |
コンパイル時間 | 4,654 ms |
コンパイル使用メモリ | 256,668 KB |
最終ジャッジ日時 | 2025-02-18 08:13:32 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 RE * 1 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 4000000000000000001int N,M,Q;using P = pair<mint,int>;P op(P a,P b){swap(a,b);a.first += b.first * mint(M).pow(a.second);a.second += b.second;return a;}P e(){return make_pair(0,0);}int main(){int K;cin>>N>>M>>K>>Q;segtree<P,op,e> seg(N);fenwick_tree<mint> F(N);rep(i,N){int a;cin>>a;a--;seg.set(i,make_pair(mint(a),1));F.add(i,mint(a));}rep(i,Q){int t;cin>>t;if(t==1){int l,r;cin>>l>>r;auto ret = seg.prod(l-1,r);mint ans = ret.first;ans *= mint(M).pow(K-ret.second+1);ans -= F.sum(l-1,r);ans /= M-1;ans += r-l;ans++;cout<<ans.val()<<endl;}else{int x,y;cin>>x>>y;x--,y--;seg.set(x,make_pair(mint(y),1));F.add(x,-F.sum(x,x+1));F.add(x,mint(y));}}return 0;}