結果

問題 No.2206 Popcount Sum 2
ユーザー Yifan Kang
提出日時 2023-05-10 11:21:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 839 ms / 4,000 ms
コード長 1,752 bytes
コンパイル時間 2,058 ms
コンパイル使用メモリ 176,560 KB
実行使用メモリ 9,528 KB
最終ジャッジ日時 2024-11-26 16:10:22
合計ジャッジ時間 14,601 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   49 |     for(auto [n,m,i] : query){
      |              ^

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
const int N = 2e5 + 5,P = 998244353,i2 = 499122177;
ll fac[N],ifac[N];
ll fpow(ll x,ll y){
    ll res = 1;
    while(y){
        if(y & 1)res = res * x % P;
        x = x * x % P;
        y >>= 1;
    }
    return res;
}
ll C(int n,int m){
    if(m < 0 || m > n)return 0;
    return fac[n] * ifac[m] % P * ifac[n - m] % P;
}
const int B = 500;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    fac[0] = 1;
    rep(i,1,N - 1)fac[i] = fac[i - 1] * i % P;
    ifac[N - 1] = fpow(fac[N - 1],P - 2);
    per(i,N - 1,1)ifac[i - 1] = ifac[i] * i % P;
    int T;cin >> T;
    vector <array<int,3>> query(T);
    rep(i,0,T - 1){
        int n,m;cin >> n >> m;
        query[i] = {n,m,i};
    }
    sort(ALL(query),[&](auto a,auto b){
        if(a[0] / B != b[0] / B)return a[0] < b[0];
        return a[1] < b[1];
    });
    int N = 0,M = 0;
    ll res = 1;
    vector <int> ans(T);
    for(auto [n,m,i] : query){
        while(N < n - 1){
            res = (2 * res - C(N,M) + P) % P;
            N++;
        }
        while(M > m - 1){
            res = (res - C(N,M) + P) % P;
            M--;
        }
        while(N > n - 1){
            N--;
            res = (res + C(N,M)) * i2 % P;
        }
        while(M < m - 1){
            M++;
            res = (res + C(N,M)) % P;
        }
        ans[i] = res * (fpow(2,n) - 1) % P;
        ans[i] = (ans[i] + P) % P;
    }
    for(int x : ans)cout << x << endl;
    return 0;
}
0