結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-02 16:07:11
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 698 ms / 4,000 ms
コード長 1,442 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,015 ms
コンパイル使用メモリ 198,840 KB
実行使用メモリ 10,720 KB
最終ジャッジ日時 2025-08-02 16:07:23
合計ジャッジ時間 12,034 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void init(int)’:
main.cpp:19:19: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   19 |         for(R int i=2;i<=x;++i)fac[i]=fac[i-1]*i%mod;
      |                   ^
main.cpp:21:19: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   21 |         for(R int i=x-1;i>1;--i)inv[i]=inv[i+1]*(i+1)%mod;
      |                   ^
main.cpp: In function ‘int main()’:
main.cpp:37:19: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   37 |         for(R int i=1;i<=T;++i)cin>>q[i].l>>q[i].r,q[i].id=i;
      |                   ^
main.cpp:39:19: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   39 |         for(R int i=1;i<=T;++i){
      |                   ^
main.cpp:46:19: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   46 |         for(R int i=1;i<=T;++i)cout<<ans[i]<<'\n';
      |                   ^

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define ll long long
#define R register
#define mk(x,y) make_pair(x,y)
#define PII pair<int,int>
using namespace std;
const int N=2e5+5,mod=998244353;
inline ll qmul(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=(a*a)%mod;b>>=1;
	}
	return ans;
}
ll fac[N],inv[N];
inline void init(int x){
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(R int i=2;i<=x;++i)fac[i]=fac[i-1]*i%mod;
	inv[x]=qmul(fac[x],mod-2);
	for(R int i=x-1;i>1;--i)inv[i]=inv[i+1]*(i+1)%mod;
}
inline ll C(ll a,ll b){
	if(a<b||b<0||a<0)return 0;
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int n,m,block,T,inv2=(mod+1)>>1,_l=1,_r=1;ll res=1;ll ans[N];
struct ASK{int l,r,id;}q[N];
inline bool cmp(ASK x,ASK y){return (x.l/block!=y.l/block)?(x.l/block<y.l/block):((x.l/block)&1)?x.r<y.r:x.r>y.r;}
inline void addl(){res=(res*2%mod-C(_l-1,_r-1)+mod)%mod;++_l;}
inline void dell(){res=(res+C(_l-2,_r-1))%mod*inv2%mod;--_l;}
inline void addr(){res=(res+C(_l-1,_r))%mod;++_r;}
inline void delr(){res=(res-C(_l-1,_r-1)+mod)%mod;--_r;}
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>T;block=(sqrt(200000));init(N-1);
	for(R int i=1;i<=T;++i)cin>>q[i].l>>q[i].r,q[i].id=i;
	sort(q+1,q+T+1,cmp);
	for(R int i=1;i<=T;++i){
		while(_l<q[i].l)addl();
		while(_l>q[i].l)dell();
		while(_r<q[i].r)addr();
		while(_r>q[i].r)delr();
		ans[q[i].id]=res*(qmul(2,q[i].l)-1+mod)%mod;
	}
	for(R int i=1;i<=T;++i)cout<<ans[i]<<'\n';
	return 0;//vj
}
0