結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-04 23:37:54
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 923 ms / 4,000 ms
コード長 1,221 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,577 ms
コンパイル使用メモリ 165,912 KB
実行使用メモリ 13,284 KB
最終ジャッジ日時 2025-08-04 23:38:09
合計ジャッジ時間 14,857 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:50:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |         scanf("%lld",&t);
      |         ~~~~~^~~~~~~~~~~
main.cpp:53:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |                 scanf("%lld %lld",&q[i].x,&q[i].y);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,mod=998244353,s=sqrt(N);
int t,n,m,fac[N],ny[N],ans[N],x,y,sum;
int ksm(int xx,int yy){
	int an=1,p=xx;
	while(yy){
		if(yy&1)an*=p;
		an%=mod;
		p*=p;
		p%=mod;
		yy>>=1;
	}
	return an;
}
int C(int xx,int yy){
	if(xx<yy)return 0;
	return fac[xx]*ny[xx-yy]%mod*ny[yy]%mod;
}
struct node{
	int x,y,id;
}q[N];
bool cmp(node x,node y){
	if(x.x/s==y.x/s)return x.y<y.y;
	return x.x/s<y.x/s; 
}
void addy(){
	sum=(sum+C(x,y+1))%mod;
	y++;
}
void dely(){
	sum=(sum+mod-C(x,y))%mod;
	y--;
}
void addx(){
	sum=(2*sum%mod+mod-C(x,y))%mod;
	x++;
}
void delx(){
	sum=(sum+C(x-1,y))%mod*ny[2]%mod;
	x--;
}
signed main(){
	fac[0]=ny[0]=1;
	for(int i=1;i<=(N-10);i++){
		fac[i]=fac[i-1]*i%mod;
		ny[i]=ksm(fac[i],mod-2);
	}
	scanf("%lld",&t);
	sum=1;
	for(int i=1;i<=t;i++){
		scanf("%lld %lld",&q[i].x,&q[i].y);
		q[i].x--;
		q[i].y--;
		q[i].id=i;
	}
	sort(q+1,q+t+1,cmp);
	for(int i=1;i<=t;i++){
		while(x<q[i].x){
			addx();
		}
		while(y>q[i].y){
			dely();
		}
		while(x>q[i].x){
			delx();
		}
		while(y<q[i].y){
			addy();	
		}
		ans[q[i].id]=sum*(ksm(2,q[i].x+1)-1)%mod;
	}
	for(int i=1;i<=t;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}
0