結果

問題 No.2206 Popcount Sum 2
ユーザー nononnonon
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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';
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0