結果

問題 No.2206 Popcount Sum 2
ユーザー roarisroaris
提出日時 2023-03-16 18:31:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,014 ms / 4,000 ms
コード長 2,878 bytes
コンパイル時間 2,574 ms
コンパイル使用メモリ 213,216 KB
実行使用メモリ 12,624 KB
最終ジャッジ日時 2024-09-18 09:27:18
合計ジャッジ時間 14,568 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 10 ms
9,012 KB
testcase_01 AC 10 ms
9,004 KB
testcase_02 AC 55 ms
9,008 KB
testcase_03 AC 55 ms
9,008 KB
testcase_04 AC 54 ms
9,008 KB
testcase_05 AC 998 ms
12,492 KB
testcase_06 AC 1,014 ms
12,496 KB
testcase_07 AC 995 ms
12,624 KB
testcase_08 AC 996 ms
12,496 KB
testcase_09 AC 992 ms
12,620 KB
testcase_10 AC 587 ms
12,492 KB
testcase_11 AC 584 ms
12,496 KB
testcase_12 AC 582 ms
12,568 KB
testcase_13 AC 532 ms
12,492 KB
testcase_14 AC 528 ms
12,624 KB
testcase_15 AC 537 ms
12,492 KB
testcase_16 AC 447 ms
12,504 KB
testcase_17 AC 448 ms
12,620 KB
testcase_18 AC 448 ms
12,620 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:38:14: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   38 |     void run(auto& add_left, auto& add_right, auto& erase_left, auto& erase_right, auto& out) {
      |              ^~~~
main.cpp:38:30: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   38 |     void run(auto& add_left, auto& add_right, auto& erase_left, auto& erase_right, auto& out) {
      |                              ^~~~
main.cpp:38:47: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   38 |     void run(auto& add_left, auto& add_right, auto& erase_left, auto& erase_right, auto& out) {
      |                                               ^~~~
main.cpp:38:65: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   38 |     void run(auto& add_left, auto& add_right, auto& erase_left, auto& erase_right, auto& out) {
      |                                                                 ^~~~
main.cpp:38:84: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   38 |     void run(auto& add_left, auto& add_right, auto& erase_left, auto& erase_right, auto& out) {
      |                                                                                    ^~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
typedef long long ll;

const int MAX = 200010;
const ll MOD = 998244353;
ll fact[MAX], finv[MAX], inv[MAX];

void Cinit() {
    fact[0] = fact[1] = 1ll;
    finv[0] = finv[1] = 1ll;
    inv[1] = 1ll;
    for (int i=2; i<MAX; i++) {
        fact[i] = fact[i-1]*i%MOD;
        inv[i] = MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i] = finv[i-1]*inv[i]%MOD;
    }
}

ll C(int n, int k) {
    if (n<k) return 0ll;
    if (n<0 || k<0) return 0ll;
    return fact[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

struct Mo {
    int N;
    vector<pair<int, int>> lr;
    
    Mo(int N) : N(N) {}
    
    void add(int l, int r) { // 0-indexed, [l, r]
        lr.emplace_back(l, r);
    }
    
    void run(auto& add_left, auto& add_right, auto& erase_left, auto& erase_right, auto& out) {
        int Q = lr.size();
        int W = N/min(N, (int)sqrt(Q)); // ブロック幅
        vector<int> ord(Q);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int x, int y) {
            int x_block = lr[x].first/W;
            int y_block = lr[y].first/W;
            if (x_block!=y_block) return x_block<y_block;
            return (x_block&1) ? lr[x].second>lr[y].second : lr[x].second<lr[y].second;
        });
        
        int l = 0;
        int r = 0;
    
        for (int i : ord) {
            while (l>lr[i].first) add_left(--l, r);
            while (r<lr[i].second) add_right(l, ++r);
            while (l<lr[i].first) erase_left(l++, r);
            while (r>lr[i].second) erase_right(l, r--);
            out(i);
        }
    }
};

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    
    Cinit();
    vector<int> pow2 = {1};
    int mult = 1;
    rep(i, 200010) {
        mult = 2*mult%MOD;
        pow2.pb((pow2.back()+mult)%MOD);
    }
    
    int T; cin >> T;
    Mo mo(200010);
    int Ns[T];
    rep(i, T) {
        int N, M; cin >> N >> M;
        mo.add(M-1, N-1);
        Ns[i] = N;
    }

    int ans[T];
    ll comb_sum = 1ll;
    
    auto add_left = [&](int l, int r) {
        comb_sum -= C(r, l+1);
        if (comb_sum<0) comb_sum += MOD;
        comb_sum %= MOD;
    };
    
    auto add_right = [&](int l, int r) {
        comb_sum = (comb_sum*2%MOD-C(r-1, l))%MOD;
        if (comb_sum<0) comb_sum += MOD;
        comb_sum %= MOD;
    };
    
    auto erase_left = [&](int l, int r) {
        comb_sum += C(r, l+1);
        comb_sum %= MOD;
    };
    
    auto erase_right = [&](int l, int r) {
        comb_sum = (comb_sum+C(r-1, l))%MOD*inv[2]%MOD;
        if (comb_sum<0) comb_sum += MOD;
        comb_sum %= MOD;
    };
    
    auto out = [&](int q) {
        ans[q] = comb_sum*pow2[Ns[q]-1]%MOD;
    };
    
    mo.run(add_left, add_right, erase_left, erase_right, out);
    rep(i, T) cout << ans[i] << endl;
}
0