結果
問題 | No.2206 Popcount Sum 2 |
ユーザー |
![]() |
提出日時 | 2024-09-13 10:59:54 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 3,709 bytes |
コンパイル時間 | 1,155 ms |
コンパイル使用メモリ | 83,976 KB |
実行使用メモリ | 634,680 KB |
最終ジャッジ日時 | 2024-09-13 11:00:21 |
合計ジャッジ時間 | 25,089 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | MLE * 1 |
other | MLE * 18 |
ソースコード
#include <vector>using namespace std;template<typename mint>struct prefix_binomial_sum {prefix_binomial_sum(int n) : size(n), b(0) {}mint get(int n, int k) {build();int m = n / b;mint res = table[m][k];m *= b;while (m < n) {res = 2 * res - binom(m, k);m++;}return res;}private:int size, b;vector<mint> fac, finv;vector<vector<mint>> table;mint binom(int n, int k) {if (n < k) return mint();return fac[n] * finv[n - k] * finv[k];}void build() {if (b > 0) return;b = 500;fac.resize(size + 1);finv.resize(size + 1);table.reserve(size / b);fac[0] = 1;for (int i = 1; i <= size; i++) {fac[i] = i * fac[i - 1];}finv[size] = fac[size].inv();for (int i = size; i >= 1; i--) {finv[i - 1] = i * finv[i];}for (int i = 0; i * b <= size; i++) {vector<mint> v(size + 1);v[0] = 1;for (int j = 1; j <= size; j++) {v[j] = v[j - 1] + binom(b * i, j);}table.push_back(v);}}};#include <algorithm>template<long long MOD>struct modint {modint() : x(0) {}modint(long long v) : x(v % MOD) {if (x < 0) x += MOD;}long long x;long long val() const { return x; }static constexpr long long mod() noexcept { return MOD; }friend modint operator+(modint a, modint b) { return a.x + b.x; }friend modint operator-(modint a, modint b) { return a.x - b.x; }friend modint operator*(modint a, modint b) { return a.x * b.x; }friend modint operator/(modint a, modint b) { return a.x * b.inv(); }friend modint operator+=(modint &a, modint b) { return a = a + b; }friend modint operator-=(modint &a, modint b) { return a = a - b; }friend modint operator*=(modint &a, modint b) { return a = a * b; }friend modint operator/=(modint &a, modint b) { return a = a / b; }friend bool operator==(modint a, modint b) {return a.x == b.x; }friend bool operator!=(modint a, modint b) {return a.x != b.x; }modint operator+() const { return *this; }modint operator-() const { return modint() - *this; }// ここまでがテンプレ// これ以降は必要に応じてmodint pow(long long k) const {modint a = x, res = 1;while (k > 0) {if (k & 1) res *= a;a *= a;k >>= 1;}return res;}modint inv() const {long long a = x, b = MOD;long long 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 u;}// ++a とか a-- とかを使うなら書くmodint& operator++() {x++;if (x == MOD ) x = 0;return *this;}modint& operator--() {if (x == 0) x = MOD;x--;return *this;}modint operator++(int) {modint res = *this;++*this;return res;}modint operator--(int) {modint res = *this;--*this;return res;}};using mint = modint<998244353>;#include <iostream>int main() {ios::sync_with_stdio(false);cin.tie(nullptr);prefix_binomial_sum<mint> C(200000);int T;cin >> T;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';}}