結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-10-10 20:36:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 415 ms / 4,000 ms
コード長 1,455 bytes
コンパイル時間 953 ms
コンパイル使用メモリ 99,736 KB
実行使用メモリ 8,376 KB
最終ジャッジ日時 2025-10-10 20:37:14
合計ジャッジ時間 8,240 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cstdint>
#include <iostream>
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;
const int N = 2e5 + 5, V = 2e5, B = 500;
const u32 P = 998244353, I2 = (P + 1) / 2;
int T, n, m;
u32 fac[N], inv[N], ans[N], cur = 1;
struct query {
    int n, m, id;
    bool operator<(const query &x) const {
        return n / B != x.n / B ? n < x.n : n / B & 1 ? m > x.m : m < x.m;
    }
} q[N];
u32 qpow(u32 a, int b) {
    u32 ret = 1;
    for (; b; b >>= 1, a = (u64)a * a % P)
        if (b & 1) ret = (u64)ret * a % P;
    return ret;
}
u32 comb(int n, int m) { return (u64)fac[n] * inv[m] % P * inv[n - m] % P; }
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    fac[0] = 1;
    for (int i = 1; i <= V; i++) fac[i] = (u64)fac[i - 1] * i % P;
    inv[V] = qpow(fac[V], P - 2);
    for (int i = V; i >= 1; i--) inv[i - 1] = (u64)inv[i] * i % P;
    cin >> T;
    for (int i = 1; i <= T; i++) cin >> q[i].n >> q[i].m, --q[i].n, --q[i].m, q[i].id = i;
    sort(q + 1, q + T + 1);
    for (int i = 1; i <= T; i++) {
        while (n < q[i].n) cur = (cur * 2 - comb(n++, m) + P) % P;
        while (m > q[i].m) (cur += P - comb(n, m--)) %= P;
        while (n > q[i].n) cur = (u64)(cur + comb(--n, m)) * I2 % P;
        while (m < q[i].m) (cur += comb(n, ++m)) %= P;
        ans[q[i].id] = (u64)(qpow(2, q[i].n + 1) - 1 + P) * cur % P;
    }
    for (int i = 1; i <= T; i++) cout << ans[i] << '\n';
}
0