結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-10-10 20:05:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 505 ms / 4,000 ms
コード長 1,151 bytes
コンパイル時間 1,690 ms
コンパイル使用メモリ 166,948 KB
実行使用メモリ 14,728 KB
最終ジャッジ日時 2025-10-10 20:05:32
合計ジャッジ時間 9,812 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:39:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   39 |         scanf("%lld",&n),bl=(int)sqrt(n);
      |         ~~~~~^~~~~~~~~~~
main.cpp:41:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   41 |                 scanf("%lld%lld",&Q[i].l,&Q[i].r),
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005,MOD=998244353;
int n,bl,fac[N],pw[N],inv[N],ans[N];
inline int KSM(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1) ans=(ans*x)%MOD;
		x=(x*x)%MOD,
		y>>=1;
	}
	return ans;
}
inline int C(int n,int m)
{
	if(n<m) return 0;
	return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
struct node
{
	int i,l,r;
	bool operator<(const node&b)const
	{
		return (l/bl!=b.l/bl)?l<b.l:((l/bl)&1?r<b.r:r>b.r);
	}
}Q[N];
signed main()
{
	pw[0]=fac[0]=1;
	for(int i=1;i<N;i++)
		fac[i]=fac[i-1]*i%MOD,
		pw[i]=pw[i-1]*2%MOD;
	inv[N-1]=KSM(fac[N-1],MOD-2); 
	for(int i=N-2;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%MOD;
	scanf("%lld",&n),bl=(int)sqrt(n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&Q[i].l,&Q[i].r),
		Q[i].i=i,Q[i].l--,Q[i].r--;
	sort(Q+1,Q+1+n);
	int l=0,r=0,now=1;
	for(int i=1;i<=n;i++)
	{
		while(Q[i].l<l) now=(now+C(--l,r))*inv[2]%MOD;
		while(Q[i].r>r) now=(now+C(l,++r))%MOD;
		while(Q[i].l>l) now=(now*2-C(l++,r))%MOD;
		while(Q[i].r<r) now=(now-C(l,r--))%MOD;
		ans[Q[i].i]=(((pw[Q[i].l+1]-1)*now%MOD)+MOD)%MOD;
	}
	for(int i=1;i<=n;i++)
		printf("%lld\n",ans[i]);
	return 0;
}
0