結果
問題 | No.2206 Popcount Sum 2 |
ユーザー |
![]() |
提出日時 | 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) { | ^~~~
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i=0; i<n; i++)#define pb push_backtypedef 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;}