結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-23 15:09:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 862 ms / 4,000 ms
コード長 1,408 bytes
コンパイル時間 1,693 ms
コンパイル使用メモリ 167,128 KB
実行使用メモリ 13,296 KB
最終ジャッジ日時 2025-08-23 15:09:55
合計ジャッジ時間 12,558 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:31:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |         scanf("%lld",&t);
      |         ~~~~~^~~~~~~~~~~
main.cpp:33:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |                 scanf("%lld%lld",&a[i].n,&a[i].m);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fuck cout<<n<<" "<<m<<" "<<aans<<endl
const int mod=998244353;
int jc[200010],invjc[200010],ans[200010],aans=2;
int L[510],R[510]; 
int B=340;
int qpow(int a,int b){
	int res=1;
	for(;b;b>>=1,a=a*a%mod)res=(res*(b&1?a:1))%mod;
	return res;
}
int C(int n,int m){return jc[n]*invjc[n-m]%mod*invjc[m]%mod;}
struct node{int n,m,id;}a[200010];
bool cmpn(node x,node y){return x.n<y.n;}
bool cmpm(node x,node y){return x.m<y.m;}
void deln(int n,int m){aans=(aans+C(n-1,m))*invjc[2]%mod;}
void delm(int n,int m){aans=(aans-C(n,m)+mod)%mod;}
void addn(int n,int m){aans=(aans*2-C(n,m)+mod)%mod;}
void addm(int n,int m){aans=(aans+C(n,m+1))%mod;}
signed main(){
	jc[0]=jc[1]=1;
	for(int i=1;i<=2e5;i++){
		jc[i]=jc[i-1]*i%mod;
		invjc[i]=qpow(i,mod-2);
	}
	invjc[0]=1;
	for(int i=1;i<=2e5;i++)invjc[i]=(invjc[i-1]*invjc[i])%mod;
	int t,res=1;
	scanf("%lld",&t);
	for(int i=1;i<=t;i++){
		scanf("%lld%lld",&a[i].n,&a[i].m);
		a[i].n--;
		a[i].m--;
		a[i].id=i;
	}
	sort(a+1,a+1+t,cmpn);
	for(int i=1;i<=(t-1)/B+1;i++)sort(a+(i-1)*B+1,a+min(i*B,t)+1,cmpm);
	int n=1,m=1;
	for(int i=1;i<=t;i++){
		while(n<a[i].n){addn(n,m);n++;}
		while(m>a[i].m){delm(n,m),m--;}
		while(n>a[i].n){deln(n,m);n--;}
		while(m<a[i].m){addm(n,m);m++;}
		ans[a[i].id]=aans*(qpow(2,a[i].n+1)-1+mod)%mod;
	}
	for(int i=1;i<=t;i++)printf("%lld\n",ans[i]);
	return 0;
}
0