結果

問題 No.3492 区間冪乗加算一点取得
コンテスト
ユーザー kwm_t
提出日時 2026-04-04 13:17:34
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 270 ms / 4,000 ms
コード長 6,698 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,806 ms
コンパイル使用メモリ 381,528 KB
実行使用メモリ 114,816 KB
最終ジャッジ日時 2026-04-04 13:17:50
合計ジャッジ時間 9,606 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:205:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
  205 | #pragma once
      |         ^~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_SEGTREE_DUAL_SEGTREE_HPP
#define KWM_T_SEGTREE_DUAL_SEGTREE_HPP

#include <vector>
#include <cassert>

/**
 * @brief Dual Segment Tree（区間作用・一点取得）
 *
 * 区間に作用を適用し、各点の値を取得するデータ構造
 *
 * 典型用途:
 *   - 区間加算 + 点取得
 *   - 区間更新（後勝ち） + 点取得
 *
 * 計算量:
 *   - apply: O(log N)
 *   - get:   O(log N)
 *
 * @tparam S モノイド
 * @tparam op 作用の合成（左から適用）
 * @tparam e 単位元
 *
 * 制約 / 注意:
 *   - op は「後から適用するものが右」に来るように設計すること
 *   - 初期値は e() が入る
 *
 * 使用例:
 *   DualSegtree<S, op, e> seg(n);
 *   seg.apply(l, r, x);
 *   auto val = seg.get(i);
 */

namespace kwm_t::segtree {

template<class S, S(*op)(S, S), S(*e)()>
struct DualSegtree {
private:
	int n = 0;        // 元のサイズ
	int size = 0;     // セグ木サイズ（2冪）
	int log = 0;      // 高さ
	std::vector<S> data;

	// 子に遅延を伝播
	void propagate(int k) {
		if (k >= size) return;
		data[k * 2] = op(data[k * 2], data[k]);
		data[k * 2 + 1] = op(data[k * 2 + 1], data[k]);
		data[k] = e();
	}

	// 根から k まで伝播
	void full_propagate(int k) {
		for (int h = log; h > 0; --h) {
			propagate(k >> h);
		}
	}

public:
	DualSegtree(int n_ = 0) : n(n_) {
		size = 1;
		log = 0;
		while (size < n) {
			size <<= 1;
			log++;
		}
		data.assign(size * 2, e());
	}

	// 点の初期化（値をリセット）
	void point_init(int p) {
		assert(0 <= p && p < n);
		p += size;
		full_propagate(p);
		data[p] = e();
	}

	// 点取得
	S get(int p) {
		assert(0 <= p && p < n);
		p += size;
		full_propagate(p);
		return data[p];
	}

	// 区間 [l, r) に作用を適用
	void apply(int l, int r, S x) {
		assert(0 <= l && l <= r && r <= n);

		l += size;
		r += size;

		if (l != size) full_propagate(l - 1);
		if (r != size * 2) full_propagate(r);

		while (l < r) {
			if (l & 1) {
				data[l] = op(data[l], x);
				++l;
			}
			if (r & 1) {
				--r;
				data[r] = op(data[r], x);
			}
			l >>= 1;
			r >>= 1;
		}
	}
};

} // namespace kwm_t::segtree

#endif // KWM_T_SEGTREE_DUAL_SEGTREE_HPP
#ifndef KWM_T_SEGTREE_DUAL_SEGTREE_VARIANTS_HPP
#define KWM_T_SEGTREE_DUAL_SEGTREE_VARIANTS_HPP

#include <algorithm>
#include <limits>

/**
 * @brief DualSegtree 用の典型パターン集
 *
 * 提供:
 *   - Range Add / Point Get
 *   - Range Update / Point Get
 *   - Range Chmin / Point Get
 *   - Range Chmax / Point Get
 *
 * 計算量:
 *   - apply: O(log N)
 *   - get:   O(log N)
 *
 * 注意:
 *   - op(x, f) は「既存作用 x に新しい作用 f を適用」
 *   - つまり op(old, new)
 *
 * verified:
 *   - 自作DualSegtreeで使用
 */

namespace kwm_t::segtree {

static constexpr long long INF = (long long)4e18;
static constexpr long long NINF = -(long long)4e18;

// ================= Range Add =================
namespace RangeAdd {
// 区間加算 / 一点取得
using S = long long;

S op(S x, S f) { return x + f; }
S e() { return 0; }
}

// ================= Range Update =================
namespace RangeUpdate {
// 区間更新（後勝ち） / 一点取得
using S = long long;
static constexpr long long ID = NINF;

S op(S x, S f) { return (f == ID ? x : f); }
S e() { return ID; }
}

// ================= Range Chmin =================
namespace RangeChmin {
// 区間chmin / 一点取得
using S = long long;

S op(S x, S f) { return std::min(x, f); }
S e() { return INF; }
}

// ================= Range Chmax =================
namespace RangeChmax {
// 区間chmax / 一点取得
using S = long long;

S op(S x, S f) { return std::max(x, f); }
S e() { return NINF; }
}

} // namespace kwm_t::segtree

#endif // KWM_T_SEGTREE_DUAL_SEGTREE_VARIANTS_HPP
#pragma once

#ifndef KWM_T_MATH_PASCAL_TABLE_HPP
#define KWM_T_MATH_PASCAL_TABLE_HPP

#include <vector>

/**
 * @brief パスカルの三角形による組み合わせテーブル構築
 *
 * n 以下のすべての C(i, j) を O(n^2) で前計算する。
 * mod を使わない（逆元不要）環境で利用可能。
 *
 * 典型用途:
 *   - long long / int での組み合わせ
 *   - mod を取らない問題
 *   - 逆元が存在しない環境
 *
 * 計算量:
 *   構築 O(n^2)
 *   クエリ O(1)
 *
 * @tparam T 数値型 (int, long long, 任意型)
 *
 * @param n 最大値
 * @return res[i][j] = C(i, j)
 *
 * 制約 / 注意:
 *   - オーバーフローに注意（特に long long）
 *   - n ≈ 5000 くらいが現実的上限（メモリ的にも）
 *
 * 使用例:
 *   auto comb = kwm_t::math::combinatorics::pascal_table<long long>(1000);
 *   cout << comb[10][3]; // 120
 *
 * verified:
 *   - typical combinatorics problems
 */
namespace kwm_t::math {

template <typename T>
std::vector<std::vector<T>> pascal_table(int n) {
	std::vector<std::vector<T>> res(n + 1, std::vector<T>(n + 1));

	for (int i = 0; i <= n; ++i) {
		res[i][0] = (T)1;
		for (int j = 1; j <= i; ++j) {
			res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
		}
	}
	return res;
}

} // namespace kwm_t::math

#endif // KWM_T_MATH_PASCAL_TABLE_HPP
using mint = atcoder::modint;
using namespace kwm_t::segtree;
using namespace kwm_t::math;
mint op(mint l, mint r) { return l + r; }
mint e() { return 0; }
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, b, q; cin >> n >> b >> q;
	mint::set_mod(b);
	auto table = pascal_table<mint>(5000);
	vector<DualSegtree<mint, op, e>> seg(101, n);
	while (q--) {
		int l, m, r; cin >> l >> m >> r;
		l--, m--;
		long long c; cin >> c;
		int d; cin >> d;
		mint tmp = 1;
		rep(i, d + 1) {
			seg[d - i].apply(l, r, table[d][i] * tmp);
			tmp *= c;
		}
		mint ans = 0;
		tmp = 1;
		rep(i, 101) {
			ans += seg[i].get(m) * tmp;
			tmp *= m + 1;
		}
		cout << ans.val() << endl;
	}
	return 0;
}
0