結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-11-17 20:58:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 562 ms / 4,000 ms
コード長 1,639 bytes
コンパイル時間 3,174 ms
コンパイル使用メモリ 283,516 KB
実行使用メモリ 9,300 KB
最終ジャッジ日時 2025-11-17 20:58:33
合計ジャッジ時間 11,566 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:34:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |         scanf("%d",&TAT);
      |         ~~~~~^~~~~~~~~~~
main.cpp:37:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   37 |                 scanf("%d%d",&n,&m);
      |                 ~~~~~^~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int ksm(int s,int cnt){
	int ret = 1;
	while(cnt){
		if(cnt&1) ret = 1ll * ret * s % mod;
		s = 1ll * s * s % mod;
		cnt >>= 1;
	}
	return ret;
}
int fac[200002], inv[200002], invfac[200002];
int C(int x,int y){
	if(x < 0 || y < 0 || x-y < 0) return 0;
	return 1ll * fac[x] * invfac[y] % mod * invfac[x-y] % mod;
}

int TAT, n, m;
struct query{
	int x, y, id;
}Q[200002];
bool cmpx(const query &a,const query &b){return a.x < b.x;}
bool cmpy(const query &a,const query &b){return a.y < b.y;}
bool cmpyf(const query &a,const query &b){return a.y > b.y;}
int Ans[200002];

int main(){
	fac[0] = 1, inv[1] = 1, invfac[0] = 1;
	for(int i=1;i<=200000;i++) fac[i] = 1ll * fac[i-1] * i % mod;
	for(int i=2;i<=200000;i++) inv[i] = 1ll * inv[mod%i] * (mod - mod/i) % mod;
	for(int i=1;i<=200000;i++) invfac[i] = 1ll * invfac[i-1] * inv[i] % mod;
	
	scanf("%d",&TAT);
	
	for(int o=1;o<=TAT;o++){
		scanf("%d%d",&n,&m);
		Ans[o] = ksm(2, n) - 1;
		Q[o].id = o;
		Q[o].x = n-1, Q[o].y = m-1;
	}
	
	sort(Q+1,Q+TAT+1,cmpx);
	int B = sqrt(TAT);
	for(int i=1;i<=TAT;i+=B){
		int R = min(TAT, i+B-1);
		if(((i-1)/B)&1) sort(Q+i,Q+R+1,cmpy);
		else sort(Q+i,Q+R+1,cmpyf);
	}
	int X = 0, Y = 0, S = 1;
	for(int i=1;i<=TAT;i++){
		while(X < Q[i].x) S = (2ll * S - C(X, Y)) % mod, X++;
		while(X > Q[i].x) S = inv[2] * (1ll * S + C(X-1, Y)) % mod, X--;
		while(Y < Q[i].y) Y++, S = (1ll * S + C(X, Y)) % mod;
		while(Y > Q[i].y) S = (1ll * S - C(X, Y)) % mod, Y--;
		Ans[Q[i].id] = 1ll * Ans[Q[i].id] * (S + mod) % mod;
	}
	
	for(int i=1;i<=TAT;i++) printf("%d\n",Ans[i]);
	
	return 0;
}
0