結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2026-08-15 19:14:34
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 397 ms / 4,000 ms
+ 730µs
コード長 2,206 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,235 ms
コンパイル使用メモリ 342,424 KB
実行使用メモリ 12,032 KB
最終ジャッジ日時 2026-08-15 19:14:46
合計ジャッジ時間 11,734 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;


const int MOD = 998244353;
const int MAXN = 200005;

long long fac[MAXN], ifac[MAXN], pow2[MAXN];

long long qpow(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}

struct Query {
    int n, m, id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

  
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--) {
        ifac[i] = ifac[i + 1] * (i + 1) % MOD;
    }
    pow2[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        pow2[i] = pow2[i - 1] * 2 % MOD;
    }
    const long long inv2 = (MOD + 1) / 2;

  
    int T;
    cin >> T;
    vector<Query> queries(T);
    for (int i = 0; i < T; i++) {
        int N, M;
        cin >> N >> M;
        queries[i] = {N - 1, M - 1, i};
    }

   
    const int blockSize = max(1, (int)sqrt(MAXN));
    sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
        int ba = a.n / blockSize, bb = b.n / blockSize;
        if (ba != bb) return ba < bb;
        return (ba & 1) ? (a.m > b.m) : (a.m < b.m);
    });

  
    vector<long long> ans(T);
    int curN = 0, curM = 0;
    long long curVal = 1; 

    for (const Query& q : queries) {
        while (curN < q.n) {  
            curVal = (2 * curVal - C(curN, curM) + MOD) % MOD;
            curN++;
        }
        while (curN > q.n) {  
            curN--;
            curVal = (curVal + C(curN, curM)) % MOD * inv2 % MOD;
        }
        while (curM < q.m) { 
            curM++;
            curVal = (curVal + C(curN, curM)) % MOD;
        }
        while (curM > q.m) { 
            curVal = (curVal - C(curN, curM) + MOD) % MOD;
            curM--;
        }
        
        ans[q.id] = (pow2[q.n + 1] - 1) % MOD * curVal % MOD;
    }

    for (long long x : ans) {
        cout << x << '\n';
    }
    return 0;
}
0