結果

問題 No.2206 Popcount Sum 2
ユーザー roaris
提出日時 2023-03-16 18:31:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,033 ms / 4,000 ms
コード長 2,878 bytes
コンパイル時間 2,251 ms
コンパイル使用メモリ 207,840 KB
最終ジャッジ日時 2025-02-11 11:54:43
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0