結果

問題 No.2206 Popcount Sum 2
ユーザー LuoFeng_Nanami
提出日時 2025-08-03 13:28:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 519 ms / 4,000 ms
コード長 2,031 bytes
コンパイル時間 2,169 ms
コンパイル使用メモリ 200,028 KB
実行使用メモリ 16,272 KB
最終ジャッジ日時 2025-08-03 13:29:07
合計ジャッジ時間 10,146 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:57:11: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   57 |         F(i, 2, maxn - 1) {
      |           ^
main.cpp:7:28: note: in definition of macro ‘F’
    7 | #define F(i, a, b) for(rll i = a; i <= b; i++)
      |                            ^
main.cpp:64:11: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   64 |         F(i, 1, q) { cin >> Q[i].l >> Q[i].r; Q[i].l--, Q[i].r--; Q[i].id = i; }
      |           ^
main.cpp:7:28: note: in definition of macro ‘F’
    7 | #define F(i, a, b) for(rll i = a; i <= b; i++)
      |                            ^
main.cpp:67:11: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   67 |         F(i, 1, q) {
      |           ^
main.cpp:7:28: note: in definition of macro ‘F’
    7 | #define F(i, a, b) for(rll i = a; i <= b; i++)
      |                            ^
main.cpp:74:11: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   74 |         F(i, 1, q) cout << ans[i] << '\n';
      |           ^
main.cpp:7:28: note: in definition of macro ‘F’
    7 | #define F(i, a, b) for(rll i = a; i <= b; i++)
      |                            ^

ソースコード

diff # 

//Fuyutsuki Saki Fan Club
//2025/06/20 11:31
//LuoFeng Nanami ver. 
#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i, a, b) for(rll i = a; i <= b; i++)
#define Fdn(i, a, b) for(rll i = a; i >= b; i--)
#define pii pair<int, int>
#define int ll
#define fi first
#define se second
#define ld long double
#define pid pair<int, ld>
#define ull unsigned ll
#define lb(x) lowbit(x)
#define lwb lower_bound
#define upb upper_bound
#define pb push_back

using namespace std;
mt19937_64 rnd(time(0));

const int inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
const ld eps = 1e-9;
const int maxn = 2e5 + 7;

int jc[maxn], inv[maxn], inj[maxn], pow2[maxn];
inline int C(int n, int m) { return ( n < m ? 0 : jc[n] * inj[m] % mod * inj[n - m] % mod ); }

int q, B;
struct query { 
	int l, r, id; 
	
	bool operator < (const query &x) const {
		return (l / B == x.l / B ? (r == x.r ? 0 : ((l / B) & 1) ^ (r < x.r)) : l < x.l);
	}
} Q[maxn]; 

int ret = 1, L, R;
int ans[maxn];

inline void LL() { (ret += C(L - 1, R)) %= mod; (ret *= inv[2]) %= mod; L--; }
inline void RL() { (ret += ret + mod - C(L, R)) %= mod; L++; }
inline void LR() { (ret += mod - C(L, R)) %= mod; R--; }
inline void RR() { (ret += C(L, R + 1)) %= mod; R++; }

signed main() {
//	freopen("saki.in", "r", stdin); 
//	freopen("saki.out", "w", stdout);
	
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	
	jc[0] = jc[1] = inv[0] = inv[1] = inj[0] = inj[1] = 1, pow2[0] = 1, pow2[1] = 2;
	F(i, 2, maxn - 1) {
		jc[i] = jc[i - 1] * i % mod;
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		inj[i] = inj[i - 1] * inv[i] % mod;
		pow2[i] = pow2[i - 1] * 2 % mod;
	}
	cin >> q; B = sqrt(q);
	F(i, 1, q) { cin >> Q[i].l >> Q[i].r; Q[i].l--, Q[i].r--; Q[i].id = i; }
	sort(Q + 1, Q + 1 + q);
	L = 0, R = 0;
	F(i, 1, q) {
		while(L > Q[i].l) LL();
		while(R < Q[i].r) RR();
		while(L < Q[i].l) RL();
		while(R > Q[i].r) LR();
		ans[Q[i].id] = ret * (pow2[Q[i].l + 1] + mod - 1) % mod;
	}
	F(i, 1, q) cout << ans[i] << '\n';
    
    
	return 0;
}
0