結果

問題 No.2206 Popcount Sum 2
ユーザー roarisroaris
提出日時 2023-03-16 17:45:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,763 bytes
コンパイル時間 2,484 ms
コンパイル使用メモリ 214,792 KB
実行使用メモリ 12,624 KB
最終ジャッジ日時 2024-09-18 09:26:06
合計ジャッジ時間 12,595 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
9,008 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 *= r*inv[r-l]%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 *= (r-l)*inv[r]%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