結果
問題 | No.2206 Popcount Sum 2 |
ユーザー |
![]() |
提出日時 | 2024-12-04 09:43:05 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 907 ms / 4,000 ms |
コード長 | 5,757 bytes |
コンパイル時間 | 2,588 ms |
コンパイル使用メモリ | 219,088 KB |
実行使用メモリ | 10,280 KB |
最終ジャッジ日時 | 2024-12-04 09:43:20 |
合計ジャッジ時間 | 14,450 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<int MOD>struct modint {modint() : x(0) {}modint(long long v) {long long y = v % m();if (y < 0) y += m();x = (unsigned int)(y);}static modint raw(int v) {modint a;a.x = v;return a;}static constexpr int mod() { return m(); }unsigned int val() const { return x; }modint& operator++() {x++;if (x == m()) x = 0;return *this;}modint& operator--() {if (x == 0) x = m();x--;return *this;}modint operator++(int) {modint res = *this;++*this;return res;}modint operator--(int) {modint res = *this;--*this;return res;}modint& operator+=(const modint &r) {x += r.x;if (x >= m()) x -= m();return *this;}modint& operator-=(const modint &r) {x -= r.x;if (x >= m()) x += m();return *this;}modint& operator*=(const modint &r) {unsigned long long y = x;y *= r.x;x = (unsigned int)(y % m());return *this;}modint &operator/=(const modint &r) {return *this = *this * r.inv();}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.x == b.x;}friend bool operator!=(const modint &a, const modint &b) {return a.x != b.x;}modint operator+() const { return *this; }modint operator-() const { return modint() - *this; }modint pow(long long k) const {assert(k >= 0);modint a = *this;modint res = 1;while (k > 0) {if (k & 1) res *= a;a *= a;k >>= 1;}return res;}modint inv() const {long long a = x, b = m(), u = 1, v = 0;while (b > 0) {long long t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}return modint(u);}private:unsigned int x;static constexpr unsigned int m() { return MOD; }};template<typename mint>struct combination {combination(int n = 0) { init(n); }mint fac(int n) {init(n);return inner_fac[n];}mint finv(int n) {init(n);return inner_finv[n];}mint inv(int n) {assert(n > 0);init(n);return inner_finv[n] * inner_fac[n - 1];}mint C(int n, int k) {if (k < 0) return 0;if (n < 0) {int sgn = (k & 1 ? -1 : 1);return sgn * C(k - n - 1, k);}if (n < k) return 0;if (n < min(1 << 25, mint::mod() - 1)) {init(n);return inner_fac[n] * inner_finv[n - k] * inner_finv[k];}init(k);mint res = inner_finv[k];for (int i = 0; i < k; i++) res *= n - i;return res;}mint P(int n, int k) {if (n < 0 || k < 0 || n < k) return 0;return inner_fac[n] * inner_finv[n - k];}mint catalan(int n) {init(2 * n);return inner_fac[2 * n] * inner_finv[n] * inner_finv[n + 1];}private:static vector<mint> inner_fac, inner_finv;static void init(int n) {int sz = inner_fac.size();if (n < sz) return;n = clamp(n, 2 * sz, min(1 << 25, mint::mod() - 1));inner_fac.resize(n + 1);inner_finv.resize(n + 1);for (int i = sz; i <= n; i++) {inner_fac[i] = i * inner_fac[i - 1];}inner_finv[n] = inner_fac[n].inv();for (int i = n; i >= sz; i--) {inner_finv[i - 1] = i * inner_finv[i];}}};template<typename mint>vector<mint> combination<mint>::inner_fac(1, 1);template<typename mint>vector<mint> combination<mint>::inner_finv(1, 1);template<typename mint>vector<mint> prefix_binomial_sum(const vector<pair<int, int>> &qs) {combination<mint> C;int q = qs.size(), m = 2;for (const auto &[n, _] : qs) m = max(m, n);vector<int> ord(q);iota(ord.begin(), ord.end(), 0);const int b = m / clamp((int)sqrt(q * 0.66), 1, m);sort(ord.begin(), ord.end(), [&](int i, int j) {auto [ni, ki] = qs[i];auto [nj, kj] = qs[j];int bi = ki / b, bj = kj / b;return bi == bj ? bi & 1 ? ni > nj : ni < nj : bi < bj;});int n = 1, k = 0;vector<mint> res(q);mint ans = 1;const mint inv2 = mint::raw(2).inv();for (int i : ord) {auto [ni, ki] = qs[i];while (k > ki) ans = ans - C.C(n, k--);while (k < ki) ans = ans + C.C(n, ++k);while (n < ni) ans = 2 * ans - C.C(n++, k);while (n > ni) ans = (ans + C.C(--n, k)) * inv2;res[i] = ans;}return res;}using mint = modint<998244353>;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int Q;cin >> Q;vector<pair<int, int>> querys(Q);for (auto &[n, k] : querys) {cin >> n >> k;n--, k--;}auto binom = prefix_binomial_sum<mint>(querys);for (int i = 0; i < Q; i++) {mint ans = mint::raw(2).pow(querys[i].first + 1) - 1;ans *= binom[i];cout << ans.val() << '\n';}}