結果
問題 | No.2206 Popcount Sum 2 |
ユーザー |
![]() |
提出日時 | 2024-12-04 10:16:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,316 ms / 4,000 ms |
コード長 | 5,838 bytes |
コンパイル時間 | 3,406 ms |
コンパイル使用メモリ | 255,972 KB |
実行使用メモリ | 5,952 KB |
最終ジャッジ日時 | 2024-12-04 10:16:33 |
合計ジャッジ時間 | 28,480 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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>struct prefix_binomial_sum {prefix_binomial_sum(int n) : size(n), b(400) { build(); }mint get(int n, int k) const {assert(0 <= n && n <= size);int tn = (n + b / 2) / b;int tk = (k + b / 2) / b;mint res = table[tn][tk];tn *= b;tk *= b;while (tk < k) res = res + C.C(tn, ++tk);while (tk > k) res = res - C.C(tn, tk--);while (tn < n) res = 2 * res - C.C(tn++, tk);while (tn > n) res = (res + C.C(--tn, tk)) * inv2;return res;}private:int size, b;mint inv2;vector<vector<mint>> table;static combination<mint> C;void build() {size += b;inv2 = mint::raw(2).inv();int n = (size + b - 1) / b;table.resize(n + 1);for (int i = 0; i <= n; i++) {table[i].resize(n + 1);table[i][0] = 1;mint cur = 1;for (int j = 1; j <= n * b; j++) {cur += C.C(b * i, j);if (j % b == 0) {table[i][j / b] = cur;}}}}};using mint = modint<998244353>;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;prefix_binomial_sum<mint> C((int)2e5);while (T--) {int N, M;cin >> N >> M;mint ans = mint(2).pow(N) - 1;ans *= C.get(N - 1, M - 1);cout << ans.val() << '\n';}}