結果
問題 | No.2571 列辞書順列 |
ユーザー |
|
提出日時 | 2023-12-02 16:27:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,511 bytes |
コンパイル時間 | 4,805 ms |
コンパイル使用メモリ | 258,032 KB |
最終ジャッジ日時 | 2025-02-18 05:26:32 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 WA * 1 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;struct Fast {Fast() {std::cin.tie(nullptr);ios::sync_with_stdio(false);cout << setprecision(10);}} fast;#define all(a) (a).begin(), (a).end()#define contains(a, x) ((a).find(x) != (a).end())#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (a); i--)#define YN(b) cout << ((b) ? "YES" : "NO") << "\n";#define Yn(b) cout << ((b) ? "Yes" : "No") << "\n";#define yn(b) cout << ((b) ? "yes" : "no") << "\n";template <typename T>ostream& operator<<(ostream& os, vector<T>& vec) {for (int i = 0; i < vec.size(); i++) {os << vec[i] << (i + 1 == vec.size() ? "" : " ");}return os;}using ll = long long;using vb = vector<bool>;using vvb = vector<vb>;using vi = vector<int>;using vvi = vector<vi>;using vl = vector<ll>;using vvl = vector<vl>;using mint = modint998244353;using vm = vector<mint>;using vvm = vector<vm>;inline ostream& operator<<(ostream& os, const mint P) { return os << P.val(); };using P = pair<mint, mint>;P op(P x, P y) { return P{x.first + y.first, x.second + y.second}; }P e() { return P{0, 0}; }void solve() {int n, m, k, q;cin >> n >> m >> k >> q;vi a(n);rep(i, 0, n) cin >> a[i];if (m == 1) {while (q--) {int type;cin >> type;if (type == 1) {int l, r;cin >> l >> r;cout << (r - l) << "\n";} else {int x, y;cin >> x >> y;a[x - 1] = y;}}} else {mint inv = mint(m).inv();vm m_pow(n + 1), inv_pow(n + 1);m_pow[0] = 1;inv_pow[0] = 1;rep(i, 0, n) {m_pow[i + 1] = m_pow[i] * m;inv_pow[i + 1] = inv_pow[i] * inv;}mint div = mint(m - 1).inv();segtree<P, op, e> seg(n);rep(i, 0, n) {a[i]--;seg.set(i, P{a[i], a[i] * inv_pow[i]});}mint pow_k = mint(m).pow(k);while (q--) {int type;cin >> type;if (type == 1) {int l, r;cin >> l >> r;l--;auto prod = seg.prod(l, r);mint u = prod.first, v = prod.second;mint ans = (v * pow_k * m_pow[l] - u) * div + r - l;cout << ans << "\n";} else {int x, y;cin >> x >> y;x--, y--;a[x] = y;seg.set(x, P{y, y * inv_pow[x]});}}}}int main() {int t = 1;// cin >> t;while (t--) solve();}