結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-11 11:18:24
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,483 bytes
コンパイル時間 2,955 ms
コンパイル使用メモリ 282,288 KB
実行使用メモリ 16,312 KB
最終ジャッジ日時 2025-08-11 11:18:40
合計ジャッジ時間 15,233 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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=0;
long long lst=1;
int n,m;
inline void add_n()
{
	n++;
	ans=ans*n%mod*rev[n-m]%mod;
	lst=lst*n%mod*rev[n-m]%mod;
}
inline void sub_n()
{
	ans=ans*(n-m)%mod*rev[n]%mod;
	lst=lst*(n-m)%mod*rev[n]%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+1)%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)%mod<<'\n';
	return 0;
}
0