結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2026-06-02 17:59:02
言語 C++17(gcc12)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,352 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,668 ms
コンパイル使用メモリ 207,140 KB
実行使用メモリ 21,732 KB
最終ジャッジ日時 2026-06-02 17:59:42
合計ジャッジ時間 11,949 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 3 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
long long nyh[1510101],cj[1510101],ans[1010111],tans=0,tn=0,m1;
long long mod=998244353;
long long poww(long long z,long long cs) {
	long long tans=1,d=z;
	while(cs) {
		if(cs%2)
			tans*=d;
		tans=tans%mod;
		cs/=2;
		d=d*d;
		d=d%mod;
	}
	return tans;
}
long long c(long long n,long long m) {
	return cj[n]*nyh[m]%mod*nyh[n-m]%mod;
}
long long s,s1,t;
struct xing {
	long long n,m,w;
};
bool  operator < (xing a,xing b) {
	if(a.n/sqrt(200000)!=b.n/sqrt(200000)) {
		return a.n/sqrt(200000)>b.n/sqrt(200000);
	} else {
		return a.m>b.m;
	}
}
priority_queue<xing> qe;
void lr() {
	tans=tans*2-c(tn-1,m1-1);
	tn++;
}
void ll() {
	tn--;
	tans=(tans+c(tn-1,m1-1))*nyh[2];
}
void rr() {
	m1++;
	tans=tans+c(tn-1,m1-1);
}
void rl() {
	tans=tans-c(tn-1,m1-1);
	m1--;
}
int main() {
	cin>>t;
	cj[0]=1;
	nyh[0]=1;
	for(int i=1; i<=360000; i++) {
		cj[i]=(cj[i-1]*i)%mod;
		nyh[i]=(nyh[i-1]*poww(i,mod-2))%mod;
	}
	for(int i=1; i<=t; i++) {
		cin>>s>>s1;
		qe.push({s,s1,i});
	}
	tn=1;
	m1=1;
	tans=1;
	while(!qe.empty()) {
		while(tn<qe.top().n)
			lr();
		while(tn>qe.top().n)
			ll();
		while(m1<qe.top().m)
			rr();
		while(m1>qe.top().m)
			rl();
		tans=tans%mod;
		ans[qe.top().w]=tans%mod*(poww(2,tn)-1)%mod;
		//cout<<qe.top().w<<endl;
		qe.pop();
	}
	for(int i=1; i<=t; i++) {
		cout<<ans[i]%mod<<endl;
	}
}
0