結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-03 00:31:20
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 1,299 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,327 ms
コンパイル使用メモリ 282,520 KB
実行使用メモリ 16,568 KB
最終ジャッジ日時 2025-08-03 00:31:32
合計ジャッジ時間 10,933 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:25:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   25 |         scanf("%d",&q);siz=sqrt(q);
      |         ~~~~~^~~~~~~~~
main.cpp:31:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |                 scanf("%d%d",&qry[i].x,&qry[i].y);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,mod=998244353,inv2=(mod+1)/2;
int fac[N],ifac[N];
int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)  res=1ll*res*a%mod;
		a=1ll*a*a%mod;b>>=1;
	}
	return res;
}
struct node{int x,y,id;}qry[N];
int q,siz,blk[N],ans[N];
bool cmp(node a,node b){
	if(blk[a.id]!=blk[b.id]) return blk[a.id]<blk[b.id];
	if(blk[a.id]&1) return a.y<b.y;
	else return a.y>b.y;
}
int c(int n,int m){
	if(n<m||m<0||n<0) return 0;
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
signed main(){
	scanf("%d",&q);siz=sqrt(q);
	fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=1ll*fac[i-1]*i%mod;
	ifac[N-1]=qpow(fac[N-1],mod-2);
	for(int i=N-2;i>=0;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
	for(int i=1;i<=q;i++){
		scanf("%d%d",&qry[i].x,&qry[i].y);
		--qry[i].x;--qry[i].y;qry[i].id=i;
	}
	for(int i=1;i<=q;i++)  blk[i]=(i-1)/siz+1;
	sort(qry+1,qry+q+1,cmp);
	for(int i=1,x=0,y=0,res=1;i<=q;i++){
		while(x<qry[i].x){
			res=(2ll*res%mod-c(x,y)+mod)%mod;
			++x;
		}
		while(x>qry[i].x){
			--x;
			res=(1ll*inv2*(res+c(x,y)))%mod;
		}
		while(y<qry[i].y){
			++y;
			res=(res+c(x,y))%mod;
		}
		while(y>qry[i].y){
			res=(res-c(x,y)+mod)%mod;
			--y;
		}
		ans[qry[i].id]=1ll*res*(qpow(2,qry[i].x+1)-1)%mod;
	}
	for(int i=1;i<=q;i++)  printf("%d\n",ans[i]);
	return 0;
}
0