結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-02 16:30:07
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,472 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,086 ms
コンパイル使用メモリ 171,408 KB
実行使用メモリ 15,708 KB
最終ジャッジ日時 2025-08-02 16:30:19
合計ジャッジ時間 11,820 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:54:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   54 |         for(auto [a,b,p]:v){
      |                  ^
main.cpp:45:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   45 |                 scanf("%d%d",&a,&b);
      |                 ~~~~~^~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
const int B=500;
const int P=998244353;
const int N=200000;
long long jie[N+5],njie[N+5],sjie[N+5],tjie[N+5];
inline long long calc(long long x,int y){
	if(!y) return 1;
	long long z=calc(x,y/2);
	return z*z%P*(y%2? x:1)%P;
}
inline long long C(long long x,long long y){
	if(x<0||y<0||x<y) return 0;
	return jie[x]*njie[y]%P*njie[x-y]%P;
}
inline long long A(long long x,long long y){
	if(x<0||y<0||x<y) return 0;
	return jie[x]*njie[x-y]%P;
}
struct quests{
	int n,m,p;
	bool operator <(quests a){
		return make_pair(n/B,m)<make_pair(a.n/B,a.m);
	}
};
long long ans[200005];
int main(){
	jie[0]=njie[0]=1;
	sjie[0]=1;
	for(int i=1;i<=N;i++){
		jie[i]=jie[i-1]*i%P;
		sjie[i]=sjie[i-1]*jie[i]%P;
	}
	tjie[N]=calc(sjie[N],P-2);
	for(int i=N-1;i>=1;i--){
		tjie[i]=tjie[i+1]*jie[i+1]%P;
	}
	for(int i=1;i<=N;i++){
		njie[i]=tjie[i]*sjie[i-1]%P;
	}
	int T;
	cin>>T;
	vector<quests> v;
	for(int i=1,a,b;i<=T;i++){
		scanf("%d%d",&a,&b);
		ans[i]=(1<<a)-1;
		quests into;
		into.n=a-1,into.m=b-1,into.p=i;
		v.push_back(into);
	}
	sort(v.begin(),v.end());
	int n=0,m=0;
	long long now=1,inv2=calc(2,P-2);
	for(auto [a,b,p]:v){
		while(n<a){
			now=(now*2%P-C(n,m)+P)%P;
			n++;
		}
		while(m<b){
			(now+=C(n,m+1))%=P;
			m++;
		}
		while(n>a){
			now=(now+C(n-1,m))*inv2%P;
			n--;
		}
		while(m>b){
			((now-=C(n,m))+=P)%=P;
			m--;
		}
		(ans[p]*=now)%=P;
	}
	for(int i=1;i<=T;i++){
		printf("%lld\n",ans[i]);
	}
	
	return 0;
}
0