結果
| 問題 | No.1549 [Cherry 2nd Tune] BANning Tuple |
| ユーザー |
 firiexp
|
| 提出日時 | 2021-06-12 00:03:07 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 292 ms / 4,000 ms |
| コード長 | 8,081 bytes |
| コンパイル時間 | 4,839 ms |
| コンパイル使用メモリ | 121,580 KB |
| 最終ジャッジ日時 | 2025-01-22 07:25:28 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
ソースコード
#include <iostream>#include <algorithm>#include <map>#include <set>#include <queue>#include <stack>#include <numeric>#include <bitset>#include <cmath>static const int MOD = 998244353;using ll = long long;using u32 = unsigned;using u64 = unsigned long long;using namespace std;template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;constexpr int ntt_mod = 998244353, ntt_root = 3;// 1012924417 -> 5, 924844033 -> 5// 998244353 -> 3, 897581057 -> 3// 645922817 -> 3;template <u32 M>struct modint {u32 val;public:static modint raw(int v) { modint x; x.val = v; return x; }modint() : val(0) {}template <class T>modint(T v) { ll x = (ll)(v%(ll)(M)); if (x < 0) x += M; val = u32(x); }modint(bool v) { val = ((unsigned int)(v) % M); }modint& operator++() { val++; if (val == M) val = 0; return *this; }modint& operator--() { if (val == 0) val = M; val--; return *this; }modint operator++(int) { modint result = *this; ++*this; return result; }modint operator--(int) { modint result = *this; --*this; return result; }modint& operator+=(const modint& b) { val += b.val; if (val >= M) val -= M; return *this; }modint& operator-=(const modint& b) { val -= b.val; if (val >= M) val += M; return *this; }modint& operator*=(const modint& b) { u64 z = val; z *= b.val; val = (u32)(z % M); return *this; }modint& operator/=(const modint& b) { return *this = *this * b.inv(); }modint operator+() const { return *this; }modint operator-() const { return modint() - *this; }modint pow(long long n) const { modint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }modint inv() const { return pow(M-2); }friend modint operator+(const modint& a, const modint& b) { return modint(a) += b; }friend modint operator-(const modint& a, const modint& b) { return modint(a) -= b; }friend modint operator*(const modint& a, const modint& b) { return modint(a) *= b; }friend modint operator/(const modint& a, const modint& b) { return modint(a) /= b; }friend bool operator==(const modint& a, const modint& b) { return a.val == b.val; }friend bool operator!=(const modint& a, const modint& b) { return a.val != b.val; }};using mint = modint<MOD>;class Factorial {vector<mint> facts, factinv;public:explicit Factorial(int n) : facts(n+1), factinv(n+1) {facts[0] = 1;for (int i = 1; i < n+1; ++i) facts[i] = facts[i-1] * mint(i);factinv[n] = facts[n].inv();for (int i = n-1; i >= 0; --i) factinv[i] = factinv[i+1] * mint(i+1);}mint fact(int k) const {if(k >= 0) return facts[k]; else return factinv[-k];}mint operator[](const int &k) const {if(k >= 0) return facts[k]; else return factinv[-k];}mint C(int p, int q) const {if(q < 0 || p < q) return 0;return facts[p] * factinv[q] * factinv[p-q];}mint P(int p, int q) const {if(q < 0 || p < q) return 0;return facts[p] * factinv[p-q];}mint H(int p, int q) const {if(p < 0 || q < 0) return 0;return q == 0 ? 1 : C(p+q-1, q);}};using mint = modint<ntt_mod>;class NTT {static constexpr int max_base = 20, maxN = 1 << max_base; // N <= 524288 * 2mint roots[maxN << 1], iroots[maxN << 1];public:NTT() {for (int i = 0; i <= max_base; ++i) {const int offset = (1 << i) - 1;const mint g = mint(ntt_root).pow((ntt_mod)/(1 << i)), ginv = g.inv();mint x = 1, y = 1;for (int j = 0; j < 1 << i; ++j) {roots[offset+j] = x;x *= g;iroots[offset+j] = y;y *= ginv;}}}void transform(vector<mint> &a, int sign){const int n = a.size();if(!sign){ // fftfor(int k = n >> 1; k >= 1; k >>= 1){for (int i = 0; i < n; i += k << 1) {for (int j = 0; j < k; ++j) {const mint tmp = a[i+j]-a[i+j+k];a[i+j] += a[i+j+k];a[i+j+k] = tmp*roots[(k << 1)-1+j];}}}}else { // ifftfor(int k = 1; k <= (n >> 1); k <<= 1){for (int i = 0; i < n; i += k << 1) {for (int j = 0; j < k; ++j) {a[i+j+k] *= iroots[(k << 1)-1+j];const mint tmp = a[i+j]-a[i+j+k];a[i+j] += a[i+j+k];a[i+j+k] = tmp;}}}const mint x = mint(n).inv();for (auto &&i : a) i *= x;}}};NTT ntt;struct poly {vector<mint> v;poly() = default;explicit poly(int n) : v(n) {};explicit poly(vector<mint> vv) : v(std::move(vv)) {};int size() const {return (int)v.size(); }poly cut(int len){if(len < v.size()) v.resize(static_cast<unsigned long>(len));return *this;}inline mint& operator[] (int i) {return v[i]; }poly& operator+=(const poly &a) {this->v.resize(max(size(), a.size()));for (int i = 0; i < a.size(); ++i) this->v[i] += a.v[i];return *this;}poly& operator-=(const poly &a) {this->v.resize(max(size(), a.size()));for (int i = 0; i < a.size(); ++i) this->v[i] -= a.v[i];return *this;}poly& operator*=(poly a) {int N = size()+a.size()-1;int sz = 1;while(sz < N) sz <<= 1;this->v.resize(sz); a.v.resize(sz);ntt.transform(this->v, 0); ntt.transform(a.v, 0);for(int i = 0; i < sz; ++i) this->v[i] *= a.v[i];ntt.transform(this->v, 1);this->v.resize(N);return *this;}poly& operator/=(const poly &a){ return (*this *= a.inv()); }poly operator+(const poly &a) const { return poly(*this) += a; }poly operator-(const poly &a) const { return poly(*this) -= a; }poly operator*(const poly &a) const { return poly(*this) *= a; }poly inv() const {int n = size();poly r(1);r[0] = (this->v[0]).inv();int k = 1;while(k < n){k *= 2;poly ff(k);for (int i = 0; i < min(k, n); ++i) {ff[i] = this->v[i];}poly nr = (r*r*ff).cut(k);for (int i = 0; i < k/2; ++i) {nr[i] = (r[i]+r[i]-nr[i]);nr[i+k/2] = -nr[i+k/2];}r = nr;}r.v.resize(n);return r;}};int main() {ll n, q;cin >> n >> q;vector<ll> k(q), a(q), b(q), s(q), t(q);for (int i = 0; i < q; ++i) {cin >> k[i] >> a[i] >> b[i] >> s[i] >> t[i];}vector<ll> z(k);sort(z.begin(), z.end());z.erase(unique(z.begin(), z.end()), z.end());for (int i = 0; i < q; ++i) {k[i] = lower_bound(z.begin(),z.end(), k[i]) - z.begin();}int m = z.size();vector<poly> v(m);for (auto &&i : v) i.v.resize(6002, 1);poly p(3001);p[0] = 1;for (int i = 1; i <= 3000; ++i) {p[i] = p[i-1]*(n+i-1)/mint(i);}vector<int> zero(m);int zeros = 0;poly tmp(3001);for (int i = 0; i < q; ++i) {for (int j = 0; j <= 3000; ++j) tmp[j] = v[k[i]][j+zero[k[i]]];p /= tmp;p.cut(3001);for (int j = a[i]; j <= b[i]; ++j) {v[k[i]][j] = 0;}zeros -= zero[k[i]];for (int j = 0; j <= 3000; ++j) {if(v[k[i]][j].val) break;zero[k[i]] = j+1;}zeros += zero[k[i]];for (int j = 0; j <= 3000; ++j) tmp[j] = v[k[i]][j+zero[k[i]]];p *= tmp;p.cut(3001);mint ans = 0;for (int j = s[i]; j <= t[i]; ++j) if(j-zeros >= 0) ans += p[j-zeros];cout << ans.val << "\n";}return 0;}