結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2026-01-29 13:41:11
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 3,033 ms / 4,000 ms
コード長 1,552 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,177 ms
コンパイル使用メモリ 343,752 KB
実行使用メモリ 16,196 KB
最終ジャッジ日時 2026-01-29 13:41:56
合計ジャッジ時間 44,291 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>

using namespace std;
#define int long long
long long rev[400001];
long long sum[400001];
constexpr int mod=998244353;
inline long long qpow(int base,int p=mod-2)
{
	long long ans=1;
	while(p)
	{
		if(p&1)
			ans=ans*base%mod;
		base=1ll*base*base%mod;
		p>>=1;
	}
	return ans;
}
constexpr int siz=447;
struct query
{
	int n,m;
	int id;
	long long ans;
	bool operator <(query t)const
	{
		if((n/siz)^(t.n/siz))
			return n<t.n;
		if((n/siz)&1)
			return m>t.m;
		return m<t.m;
	}
}q[200010];
long long ans=1;
long long lst=1;
int n,m;
//2S(n,m)-C_{n}^m=S(n+1,m)
inline void add_n()
{
	n++;
	ans=(2*ans-lst+mod)%mod;
	lst=lst*n%mod*rev[n-m]%mod;
}
//S(n-1,m)=\frac{S(n,m)+C_{n-1}^m}{2}
inline void sub_n()
{
	lst=lst*(n-m)%mod*rev[n]%mod;
	//lst=C_{n-1}^m
	ans=(ans+lst)*qpow(2)%mod;
	n--;
}
inline void add_m()
{
	m++;
	lst=lst*(n-m+1)%mod*rev[m]%mod;
	ans=(ans+lst)%mod;
}
inline void sub_m()
{
	ans=(ans-lst+mod)%mod;
	lst=lst*rev[n-m+1]%mod*m%mod;
	m--;
}
signed main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	sum[0]=rev[0]=1;
	for(int i=1;i<=400000;i++)
	{
		rev[i]=qpow(i)%mod;
	}
	int t;cin>>t;
	for(int i=1;i<=t;i++)
	{
		cin>>q[i].n>>q[i].m;
		q[i].n--,q[i].m--;
		q[i].id=i;
	}
	sort(q+1,q+1+t);
	n=1;
	for(int i=1;i<=t;i++)
	{
		while(n<q[i].n)
			add_n();
		while(m>q[i].m)
			sub_m();
		while(m<q[i].m)
			add_m();
		while(n>q[i].n)
			sub_n();
		q[i].ans=(ans)%mod;
	}
	sort(q+1,q+1+t,[](query a,query b){return a.id<b.id;});
	for(int i=1;i<=t;i++)
		cout<<q[i].ans*(qpow(2,q[i].n+1)-1)%mod<<'\n';
	return 0;
}
0