結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-02 21:11:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,024 ms / 4,000 ms
コード長 1,271 bytes
コンパイル時間 3,458 ms
コンパイル使用メモリ 281,472 KB
実行使用メモリ 10,800 KB
最終ジャッジ日時 2025-08-02 21:11:58
合計ジャッジ時間 14,669 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:28:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   28 |         scanf("%d",&q);
      |         ~~~~~^~~~~~~~~
main.cpp:30:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   30 |                 scanf("%d%d",&a[i].r,&a[i].l),a[i].l--,a[i].r--,a[i].id=i,b[i]=a[i].r+1;
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
int B,qu[200010],fac[200010],inv[200010],inve[200010],b[200010],pw[200010];
const int P=998244353;
struct Node{
	int l,r,id;
	bool operator <(const Node &A)
	{
		if(l/B!=A.l/B) return l/B<A.l/B;
		return r<A.r;
	}
}a[200010];
int C(int aa,int bb)
{
	return 1LL*fac[aa]*inve[bb]%P*inve[aa-bb]%P;
}
int q;
int main()
{
	fac[0]=fac[1]=inv[1]=inve[0]=inve[1]=pw[0]=1,pw[1]=2;
	for(int i=2;i<=200000;i++)
	{
		fac[i]=1LL*fac[i-1]*i%P;
		inv[i]=1LL*(P-P/i)*inv[P%i]%P;
		inve[i]=1LL*inve[i-1]*inv[i]%P;
		pw[i]=2*pw[i-1]%P;
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
		scanf("%d%d",&a[i].r,&a[i].l),a[i].l--,a[i].r--,a[i].id=i,b[i]=a[i].r+1;
	B=400;
	sort(a+1,a+q+1);
	int ans=0;
	for(int i=0;i<=a[1].l;i++) ans=(ans+C(a[1].r,i))%P;
	qu[a[1].id]=ans;
	for(int i=2;i<=q;i++)
	{
		for(int j=a[i].l+1;j<=a[i-1].l;j++) ans=(ans-C(a[i-1].r,j)+P)%P;
		for(int j=a[i-1].r+1;j<=a[i].r;j++) ans=(2*ans%P-C(j-1,min(a[i].l,a[i-1].l))+P)%P;
//		printf("%d\n",ans);
		for(int j=a[i-1].l+1;j<=a[i].l;j++) ans=(ans+C(max(a[i-1].r,a[i].r),j))%P;
		for(int j=a[i-1].r;j>a[i].r;j--) ans=1LL*(ans+C(j-1,a[i].l))*((P+1)/2)%P;
		qu[a[i].id]=ans;
	}
//	printf("%d\n",b[1]);
	for(int i=1;i<=q;i++) printf("%lld\n",1LL*qu[i]*(pw[b[i]]-1+P)%P);
	return 0;
}
0