結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-23 13:14:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,404 bytes
コンパイル時間 1,660 ms
コンパイル使用メモリ 166,752 KB
実行使用メモリ 12,916 KB
最終ジャッジ日時 2025-08-23 13:14:32
合計ジャッジ時間 9,458 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘long long int deln(long long int, long long int)’:
main.cpp:18:57: warning: no return statement in function returning non-void [-Wreturn-type]
   18 | int deln(int n,int m){aans=(aans+C(n-1,m))*invjc[2]%mod;}
      |                                                         ^
main.cpp: In function ‘long long int delm(long long int, long long int)’:
main.cpp:19:50: warning: no return statement in function returning non-void [-Wreturn-type]
   19 | int delm(int n,int m){aans=(aans-C(n,m)+mod)%mod;}
      |                                                  ^
main.cpp: In function ‘long long int addn(long long int, long long int)’:
main.cpp:20:52: warning: no return statement in function returning non-void [-Wreturn-type]
   20 | int addn(int n,int m){aans=(aans*2-C(n,m)+mod)%mod;}
      |                                                    ^
main.cpp: In function ‘long long int addm(long long int, long long int)’:
main.cpp:21:48: warning: no return statement in function returning non-void [-Wreturn-type]
   21 | int addm(int n,int m){aans=(aans+C(n,m+1))%mod;}
      |                                                ^
main.cpp: In function ‘int main()’:
main.cpp:31:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |         scanf("%lld",&t);
      |         ~~~~~^~~~~~~~~~~
main.cpp:33:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |                 scanf("%lld%lld",&a[i].n,&a[i].m);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fuck cout<<n<<" "<<m<<" "<<aans<<endl
const int mod=998244353;
int jc[200010],invjc[200010],ans[200010],aans=2;
int L[510],R[510]; 
int B=340;
int qpow(int a,int b){
	int res=1;
	for(;b;b>>=1,a=a*a%mod)res=(res*(b&1?a:1))%mod;
	return res;
}
int C(int n,int m){return jc[n]*invjc[n-m]%mod*invjc[m]%mod;}
struct node{int n,m,id;}a[200010];
bool cmpn(node x,node y){return x.n<y.n;}
bool cmpm(node x,node y){return x.m<y.m;}
int deln(int n,int m){aans=(aans+C(n-1,m))*invjc[2]%mod;}
int delm(int n,int m){aans=(aans-C(n,m)+mod)%mod;}
int addn(int n,int m){aans=(aans*2-C(n,m)+mod)%mod;}
int addm(int n,int m){aans=(aans+C(n,m+1))%mod;}
signed main(){
	jc[0]=jc[1]=1;
	for(int i=1;i<=2e5;i++){
		jc[i]=jc[i-1]*i%mod;
		invjc[i]=qpow(i,mod-2);
	}
	invjc[0]=1;
	for(int i=1;i<=2e5;i++)invjc[i]=(invjc[i-1]*invjc[i])%mod;
	int t,res=1;
	scanf("%lld",&t);
	for(int i=1;i<=t;i++){
		scanf("%lld%lld",&a[i].n,&a[i].m);
		a[i].n--;
		a[i].m--;
		a[i].id=i;
	}
	sort(a+1,a+1+t,cmpn);
	for(int i=1;i<=(t-1)/B+1;i++)sort(a+(i-1)*B+1,a+min(i*B,t)+1,cmpm);
	int n=1,m=1;
	for(int i=1;i<=t;i++){
		while(n<a[i].n){addn(n,m);n++;}
		while(m>a[i].m){delm(n,m),m--;}
		while(n>a[i].n){deln(n,m);n--;}
		while(m<a[i].m){addm(n,m);m++;}
		ans[a[i].id]=aans*(qpow(2,a[i].n+1)-1+mod)%mod;
	}
	for(int i=1;i<=t;i++)printf("%lld\n",ans[i]);
	return 0;
}
0