結果
| 問題 | No.3492 区間冪乗加算一点取得 |
| コンテスト | |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2026-04-03 22:05:20 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 58 ms / 4,000 ms |
| コード長 | 5,734 bytes |
| 記録 | |
| コンパイル時間 | 990 ms |
| コンパイル使用メモリ | 102,576 KB |
| 実行使用メモリ | 7,976 KB |
| 最終ジャッジ日時 | 2026-04-03 22:05:34 |
| 合計ジャッジ時間 | 2,082 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge4_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 27 |
ソースコード
#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }
#include <cassert>
#include <utility>
namespace nachia{
// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
long long x = 1, y = 0;
while(b){
long long u = a / b;
std::swap(a-=b*u, b);
std::swap(x-=y*u, y);
}
return std::make_pair(x, a);
}
} // namespace nachia
namespace nachia{
class DynamicModSupplier{
using u64 = unsigned long long;
using Int = unsigned int;
private:
u64 imod;
Int mod;
// atcoder library
u64 reduce2(u64 z) const noexcept {
// atcoder library
#ifdef _MSC_VER
u64 x; _umul128(z, im, &x);
#else
using u128 = unsigned __int128;
u64 x = (u64)(((u128)(z)*imod) >> 64);
#endif
return z - x * mod;
}
public:
DynamicModSupplier(unsigned int MOD = 998244353) : mod(MOD) {
assert(2 <= MOD);
assert(MOD < (1u << 31));
imod = (u64)(-1) / mod + 1;
}
Int reduce(u64 z) const noexcept {
Int v = reduce2(z);
if(mod <= v) v += mod;
return v;
}
Int add(Int a, Int b) const { a += b; if(a >= mod){ a -= mod; } return a; }
Int sub(Int a, Int b) const { a -= b; if(a >= mod){ a += mod; } return a; }
Int mul(Int a, Int b) const { return reduce((u64)a * b); }
Int muladd(Int a, Int b, Int c) const { return reduce((u64)a * b + c); }
Int inv(Int a) const {
Int v = ExtGcd(a, mod).first;
return (v < mod) ? v : (v + mod);
}
Int pow(Int a, u64 i) const {
Int r = a, ans = 1;
while(i){
if(i & 1) ans = mul(ans, r);
i /= 2;
r = mul(r, r);
}
return ans;
}
Int getMod() const { return mod; }
};
} // namespace nachia
namespace nachia{
template<unsigned int IDENTIFER, class IDENTIFER2 = void>
class DynamicModint{
using Int = unsigned int;
using MyType = DynamicModint;
private:
static DynamicModSupplier _c;
Int v;
template< class Elem >
static Elem SafeMod(Elem x, Int mod){
if(x < 0){
if(0 <= x+mod) return x + mod;
return mod - ((-(x+mod)-1) % mod + 1);
}
return x % mod;
}
public:
DynamicModint() : v(0) {}
DynamicModint(const MyType& r) : v(r.v) {}
MyType& operator=(const MyType&) = default;
DynamicModint(long long x){ v = SafeMod(x, _c.getMod()); }
static MyType raw(Int _v){ MyType res; res.v = _v; return res; }
static void setMod(DynamicModSupplier sup){ _c = std::move(sup); }
MyType operator+=(MyType r){ return v = _c.add(v, r.v); }
MyType operator+(MyType r) const { return raw(_c.add(v, r.v)); }
MyType operator-=(MyType r){ return v = _c.sub(v, r.v); }
MyType operator-(MyType r) const { return raw(_c.sub(v, r.v)); }
MyType operator-() const { return raw(v ? _c.getMod()-v : 0); }
MyType operator*=(MyType r){ return v = _c.mul(v, r.v); }
MyType operator*(MyType r) const { return raw(_c.mul(v, r.v)); }
MyType operator/=(MyType r){ return v = _c.mul(v, _c.inv(r.v)); }
MyType operator/(MyType r) const { return raw(_c.mul(v, _c.inv(r.v))); }
MyType inv() const { return raw(_c.inv(v)); }
MyType pow(unsigned long long r) const { return raw(_c.pow(v, r)); }
MyType mulAdd(MyType mul, MyType add) const { return raw(_c.muladd(v, mul.v, add.v)); }
Int val() const { return v; }
Int operator*() const { return v; }
static Int mod(){ return _c.getMod(); }
};
template<unsigned int IDENTIFER, class IDENTIFER2>
DynamicModSupplier DynamicModint<IDENTIFER, IDENTIFER2>::_c;
} // namespace nachia
using Mint = nachia::DynamicModint<998244353>;
namespace nachia {
template <class T> struct FenwickTree {
public:
FenwickTree() : _n(0){}
explicit FenwickTree(int n, T ZERO = T(0)) : _n(n), a(n, ZERO){}
void add(int p, T x){
assert(0 <= p && p < _n);
p++;
while(p <= _n){
a[p-1] += T(x);
p += p & -p;
}
}
T sum(int r){
return sumr(r);
}
T sum(int l, int r){
return sumr(r) - sumr(l);
}
private:
int _n;
std::vector<T> a;
T sumr(int r){
T s = 0;
while(r > 0){
s += a[r-1];
r -= r & -r;
}
return s;
}
};
} // namespace nachia
namespace nachia {
template<class T> using PointAddRangeSumFwt = FenwickTree<T>;
} // namespace nachia
void testcase(){
ll N, B, Q; cin >> N >> B >> Q;
Mint::setMod(B);
ll Z = 101;
V<nachia::PointAddRangeSumFwt<Mint>> A(Z, nachia::PointAddRangeSumFwt<Mint>(N+1));
V<V<Mint>> comb(Z, V<Mint>(Z));
REP(i,Z){
comb[i][0] = comb[i][i] = 1;
for(ll j=1; j<i; j++) comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
}
REP(qi,Q){
ll l, m, r, c, d; cin >> l >> m >> r >> c >> d; l--;
Mint h = 1, cc = c;
REP(i,d+1){
A[d-i].add(l, h * comb[d][i]);
A[d-i].add(r, -h * comb[d][i]);
h *= cc;
}
Mint ans = 0;
h = 1; cc = m;
REP(i,Z){
ans += A[i].sum(m) * h;
h *= cc;
}
cout << ans.val() << "\n";
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
testcase();
return 0;
}