結果
問題 |
No.2206 Popcount Sum 2
|
ユーザー |
![]() |
提出日時 | 2025-08-11 10:00:52 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,483 bytes |
コンパイル時間 | 4,993 ms |
コンパイル使用メモリ | 280,352 KB |
実行使用メモリ | 11,392 KB |
最終ジャッジ日時 | 2025-08-11 10:01:11 |
合計ジャッジ時間 | 16,210 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | WA * 18 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long long long rev[200001]; long long sum[200001]; 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<=200000;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; }