結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-02 16:21:20
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 778 ms / 4,000 ms
コード長 1,315 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,331 ms
コンパイル使用メモリ 282,336 KB
実行使用メモリ 9,296 KB
最終ジャッジ日時 2025-08-02 16:21:35
合計ジャッジ時間 13,643 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:46:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   46 |         scanf("%d",&T);
      |         ~~~~~^~~~~~~~~
main.cpp:47:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   47 |         for(int i=1;i<=T;i++) scanf("%d%d",&Qs[i].n,&Qs[i].m),mx=max(mx,Qs[i].n),Qs[i].id=i;
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int mod=998244353;
const int pw2=(mod+1)/2;
typedef long long ll;
int T,mx;
int in[N];
int fac[N],inv[N];
struct Query{
	int n,m,id; 
} Qs[N];
int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=(ll)res*a%mod;
		a=(ll)a*a%mod;
		b>>=1;
	}
	return res;
}
bool cmp(Query A,Query B){
	return (in[A.n]!=in[B.n]?A.n<B.n:A.m<B.m);
}
int C(int n,int m){
	return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int nn=1,mm=1,res=1,ans[N];
void add1(){
	res=((res*2-C(nn-1,mm-1))%mod+mod)%mod;
	++nn;
}
void add2(){
	res=(res+C(nn-1,mm))%mod;
	++mm;
}
void del1(){
	--nn;
	res=(ll)(res+C(nn-1,mm-1))*pw2%mod;
}
void del2(){
	--mm;
	res=(res-C(nn-1,mm)+mod)%mod; 
}
int main(){
	scanf("%d",&T);
	for(int i=1;i<=T;i++) scanf("%d%d",&Qs[i].n,&Qs[i].m),mx=max(mx,Qs[i].n),Qs[i].id=i;
	fac[0]=1;for(int i=1;i<=mx;i++) fac[i]=(ll)fac[i-1]*i%mod;
	inv[mx]=qpow(fac[mx],mod-2);for(int i=mx-1;i>=0;i--) inv[i]=(ll)inv[i+1]*(i+1)%mod;
	int sq=sqrt(mx);
	for(int i=1;i<=mx;i++) in[i]=(i-1)/sq+1;
	sort(Qs+1,Qs+T+1,cmp);
	for(int i=1;i<=T;i++){
		while(nn<Qs[i].n) add1();
		while(mm<Qs[i].m) add2();
		while(nn>Qs[i].n) del1();
		while(mm>Qs[i].m) del2();
		ans[Qs[i].id]=(ll)(qpow(2,Qs[i].n)-1)*res%mod;
	}
	for(int i=1;i<=T;i++) printf("%d\n",ans[i]);
	return 0;
}
0