結果

問題 No.2206 Popcount Sum 2
ユーザー Yifan KangYifan 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
6,656 KB
testcase_01 AC 5 ms
6,656 KB
testcase_02 AC 140 ms
6,656 KB
testcase_03 AC 140 ms
6,656 KB
testcase_04 AC 140 ms
6,656 KB
testcase_05 AC 822 ms
9,308 KB
testcase_06 AC 839 ms
9,440 KB
testcase_07 AC 829 ms
9,344 KB
testcase_08 AC 831 ms
9,436 KB
testcase_09 AC 827 ms
9,528 KB
testcase_10 AC 517 ms
9,432 KB
testcase_11 AC 510 ms
9,436 KB
testcase_12 AC 507 ms
9,436 KB
testcase_13 AC 466 ms
9,472 KB
testcase_14 AC 479 ms
9,472 KB
testcase_15 AC 464 ms
9,440 KB
testcase_16 AC 563 ms
9,472 KB
testcase_17 AC 553 ms
9,312 KB
testcase_18 AC 561 ms
9,472 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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