結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10,mod=998244353,B=320,INV2=(mod+1)/2;
int n,m,bin[N],ans[N],ord[N];
int fac[N],inv[N],invp[N];
struct node
{
	int l,r,o;
	bool operator<(const node &x)const
	{
		if (ord[l]==ord[x.l]) return ord[l]&1?r<x.r:r>x.r;
		return l<x.l;
	}
}a[N];
int qpow(int bas,int ind)
{
	int prd=1;
	for (;ind;ind>>=1)
	{
		if (ind&1) prd=1ll*prd*bas%mod;
		bas=1ll*bas*bas%mod;
	}
	return prd;
}
int C(int x,int y)
{
	if (y<0||x>y) return 0;
	return 1ll*fac[y]*invp[x]%mod*invp[y-x]%mod;
}
int main()
{
	n=2e5;
	for (int i=1;i<=n;i++) ord[i]=(i-1)/B+1;
	bin[0]=1;
	for (int i=1;i<=n;i++) bin[i]=2*bin[i-1]%mod;
	fac[0]=inv[0]=invp[0]=1;
	fac[1]=inv[1]=invp[1]=1;
	for (int i=2;i<=n;i++)
		fac[i]=1ll*fac[i-1]*i%mod,
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod,
		invp[i]=1ll*invp[i-1]*inv[i]%mod;
	cin>>m;
	for (int i=1;i<=m;i++) scanf("%d%d",&a[i].r,&a[i].l),ans[i]=bin[a[i].r]-1,a[i].o=i,a[i].l--,a[i].r--;
	sort(a+1,a+m+1);
	int l,r,res=1;
	l=0,r=1;
	for (int i=1;i<=m;i++)
	{
		if (!a[i].r) continue;
		while (r<a[i].r) res=(2ll*res+mod-C(l,r))%mod,r++;
		while (l>a[i].l) (res+=mod-C(l,r))%=mod,l--;
		while (r>a[i].r) r--,res=1ll*(res+C(l,r))*INV2%mod;
		while (l<a[i].l) l++,(res+=C(l,r))%=mod;
//		cerr<<a[i].o<<" "<<res<<endl;
		ans[a[i].o]=1ll*ans[a[i].o]*res%mod;
	}
	for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}
0