結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-02 20:13:40
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 834 ms / 4,000 ms
コード長 3,026 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,980 ms
コンパイル使用メモリ 282,156 KB
実行使用メモリ 21,724 KB
最終ジャッジ日時 2025-08-02 20:13:56
合計ジャッジ時間 15,435 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// ???????
// ???????????????????????i????
// ????n - 1?????m - 1?????????? ?(i = 0...m-1) C(n-1, i)
// ????????????????????(2^n - 1) * (?(i = 0...m-1) C(n-1, i))
// ???????????????????????????????FFT??NTT???
// ?????????????????????????????????????
// ??(2 ^ n - 1)?????????????????F(n, m)?????
// ???F(n, m) -> F(n, m + 1)???????C(n - 1, m)
// ???F(n, m) -> F(n + 1, m)?????????1??????
// ????????????????????n???m??????????n + 1??m?
//      o   o   o   o   o
//     / \ / \ / \ / \ /   \ 
//    o   o   o   o   o     o
// ??????????????????? 2 * F(n, m)?????C(n, m)???????? (?????????)
// ???????C(n, m)??
// ???????????

#include <bits/stdc++.h>

#define int long long
#define IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define fi first
#define se second
#define PII pair<int, int>
#define PDD pair<double, double>
#define LL long long
#define mem(a, b) memset(a, b, sizeof a)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define Array(a) vector<array<int, a>>

using namespace std;

const double eps = 1e-8;
const int N = 300005, M = 500005, INF = 0x3f3f3f3f;
const int Mod = 998244353;

int T;
int ans[N], res, pw[N];
int A[N], inv[N];
int belong[N];
struct Que {
    int l, r, id;
    bool operator < (const Que &X) const {
        return belong[l] != belong[X.l] ? (l < X.l) : (belong[l] & 1 ? r < X.r : r > X.r);
    }
}e[N];

inline int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (res * a) % Mod;
        a = (a * a) % Mod;
        b >>= 1;
    }
    return res;
} 

inline void init() {
    A[0] = 1;
    for (int i = 1; i < N; i++) A[i] = A[i - 1] * i % Mod;
    inv[0] = 1;
    for (int i = 1; i < N; i++) inv[i] = qpow(A[i], Mod - 2);
    pw[0] = 1;
    for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * 2 % Mod;
    return ;
}

inline int C(int X, int Y) {
    return (A[X] * inv[Y]) % Mod * inv[X - Y] % Mod;
}

signed main() {
    IO;
    init();
    cin >> T;
    for (int i = 1; i <= T; i++) cin >> e[i].l >> e[i].r, e[i].id = i, e[i].l--, e[i].r--;
    int Block = sqrt(2e5);
    for (int i = 1; i <= 200000; i++) belong[i] = (i - 1) / Block + 1;
    sort(e + 1, e + T + 1);

    int l = 0, r = -1;
    for (int i = 1; i <= T; i++) {
        // cout << i << " " << e[i].l << " " << e[i].r << '\n';
        int L = e[i].l, R = e[i].r;
        while (l < L) {
            res = res * 2 % Mod;
            res -= C(l, r);
            res = (res % Mod + Mod) % Mod;
            l++;
        }
        while (l > L) {
            l--;
            res = (res + C(l, r)) % Mod;
            res = res * inv[2] % Mod;
        }
        while (r < R) {
            r++;
            res += C(l, r);
            res = (res % Mod + Mod) % Mod;
        }
        while (r > R) {
            res -= C(l, r);
            res = (res % Mod + Mod) % Mod;
            r--;
        }
        // cout << res << '\n';

        ans[e[i].id] = res * (pw[e[i].l + 1] - 1 % Mod) % Mod;
    }

    for (int i = 1; i <= T; i++) cout << ans[i] << '\n';
    return 0;
}
0