結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-02 16:51:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,736 ms / 4,000 ms
コード長 3,492 bytes
コンパイル時間 1,798 ms
コンパイル使用メモリ 169,068 KB
実行使用メモリ 10,812 KB
最終ジャッジ日時 2025-08-02 16:51:52
合計ジャッジ時間 20,974 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:82:48: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘Mint::mint’ [-Wformat=]
   82 |         for (int i = 1; i <= Q; i++) printf ("%d\n", ans[i]);
      |                                               ~^     ~~~~~~
      |                                                |          |
      |                                                int        Mint::mint

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 300005
il int rd(){
	int s = 0, w = 1;
	char ch = getchar();
	for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
	for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
	return s * w;
}
namespace Mint{
	const int P = 998244353;
	class mint {public:
		int num;
		mint() = default;
		mint(int _num) : num((_num % P + P) % P) {}
		mint &operator = (int b) {return *this = mint(b);}
		friend bool operator <(mint a, mint b){return a.num < b.num;}
		friend bool operator >(mint a, mint b){return a.num > b.num;}
		friend bool operator <=(mint a, mint b){return a.num <= b.num;}
		friend bool operator >=(mint a, mint b){return a.num >= b.num;}
		friend bool operator ==(mint a, mint b){return a.num == b.num;}
		friend mint operator +(mint a, mint b){return mint((a.num + b.num) % P);}
		friend mint &operator +=(mint &a, mint b){return a = a + b;}
		friend mint operator +(mint a, int b){return a + mint(b);}
		friend mint &operator +=(mint &a, int b){return a = a + b;}
		friend mint &operator ++(mint &a){return a += 1;}
		friend mint operator ++(mint &a,int){mint copy(a);a += 1;return copy;}
		friend mint operator -(mint a, mint b){return mint(((a.num - b.num) % P + P) % P);}
		friend mint &operator -=(mint &a, mint b){return a = a - b;}
		friend mint operator -(mint a, int b){return a - mint(b);}
		friend mint &operator -=(mint &a, int b){return a = a - b;}
		friend mint &operator --(mint &a){return a -= 1;}
		friend mint operator --(mint &a,int){mint copy(a);a -= 1;return copy;}
		friend mint operator *(mint a, mint b){return mint((ll)a.num * b.num % P);}
		friend mint &operator *=(mint &a, mint b){return a = a * b;}
		friend mint operator *(mint a, int b){return a * mint(b);}
		friend mint &operator *=(mint &a, int b){return a = a * b;}
		mint inv(){ll ans = 1, x = num, r = P - 2;for (; r; x = x * x % P, r >>= 1) if (r & 1) ans = ans * x % P;return ans;}
		friend mint operator /(mint a, mint b){return a * b.inv();}
		friend mint &operator /=(mint &a, mint b){return a = a / b;}
		friend mint operator /(mint a, int b){return a / mint(b);}
		friend mint &operator /=(mint &a, int b){return a = a / b;}
	};
	mint ksm(mint x, ll r){mint ans = 1;for (; r; x = x * x, r >>= 1) if (r & 1) ans = ans * x;return ans;}
}
using namespace Mint;
mint fact[N], inft[N];
il void init(int n){
	fact[0] = 1;
	for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
	inft[n] = ksm(fact[n], P - 2);
	for (int i = n; i >= 1; i--) inft[i - 1] = inft[i] * i;
}
il mint C(int n, int m){return (m < 0 || n < m) ? 0 : fact[n] * inft[m] * inft[n - m];}
const int B = 500, inv2 = 499122177;
int n, m, Q;
mint val, ans[N];
struct Node{
	int n, m, id;
}q[N];
il bool cmp(Node a, Node b){return (a.n / B) != (b.n / B) ? a.n < b.n : a.m < b.m;}
il void addn(int n){val = val + val - C(n - 1, m);}
il void deln(int n){val = (val + C(n - 1, m)) * inv2;}
il void addm(int m){val += C(n, m);}
il void delm(int m){val -= C(n, m);}
signed main(){
	init(300000);
	Q = rd();
	for (int i = 1; i <= Q; i++) q[i] = Node{rd() - 1, rd() - 1, i};
	sort (q + 1, q + Q + 1, cmp);
	n = 0, m = 0, val = 1;
	for (int i = 1; i <= Q; i++){
		while (n < q[i].n) addn(++n);
		while (n > q[i].n) deln(n--);
		while (m < q[i].m) addm(++m);
		while (m > q[i].m) delm(m--);
		ans[q[i].id] = val * (ksm(2, n + 1) - 1);
	}
	for (int i = 1; i <= Q; i++) printf ("%d\n", ans[i]);
	return 0;
}
0