結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-11 11:47:16
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 537 ms / 4,000 ms
コード長 1,510 bytes
コンパイル時間 3,270 ms
コンパイル使用メモリ 282,588 KB
実行使用メモリ 16,160 KB
最終ジャッジ日時 2025-08-11 11:47:29
合計ジャッジ時間 12,403 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int kMaxN = 2e5 + 5, kM = 998244353;

int T, B, ans[kMaxN], p[kMaxN], fac[kMaxN], inv[kMaxN], ifac[kMaxN], ret = 1;

struct Q {
  int n, m, i;
} q[kMaxN];

void Init() {
  p[0] = fac[0] = 1;
  for (int i = 1; i < kMaxN; i++) {
    p[i] = 2 * p[i - 1] % kM;
    fac[i] = 1LL * i * fac[i - 1] % kM;
  }
  ifac[0] = ifac[1] = inv[1] = 1;
  for (int i = 2; i < kMaxN; i++) {
    inv[i] = 1LL * (kM - kM / i) * inv[kM % i] % kM;
    ifac[i] = 1LL * inv[i] * ifac[i - 1] % kM;
  }
}

int Binom(int m, int n) {
  if (m < n) return 0;
  return 1LL * fac[m] * ifac[n] % kM * ifac[m - n] % kM;
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  Init();
  cin >> T, B = sqrt(T);
  for (int i = 1; i <= T; i++) {
    cin >> q[i].n >> q[i].m, q[i].i = i;
  }
  sort(q + 1, q + 1 + T, [](Q x, Q y) {
    if (x.n / B != y.n / B) return x.n / B < y.n / B;
    return x.n / B % 2 ? x.m < y.m : x.m > y.m;
  });
  for (int i = 1, N = 1, M = 1; i <= T; i++) {
    for (; N < q[i].n; N++) {
      ret = (2LL * ret - Binom(N - 1, M - 1) + kM) % kM;
    }
    for (; N > q[i].n; N--) {
      ret = 1LL * (ret + Binom(N - 2, M - 1)) * inv[2] % kM;
    }
    for (; M < q[i].m; M++) {
      ret = (ret + Binom(N - 1, M)) % kM;
    }
    for (; M > q[i].m; M--) {
      ret = (ret - Binom(N - 1, M - 1) + kM) % kM;
    }
    ans[q[i].i] = 1LL * (p[N] - 1) * ret % kM;
  }
  for (int i = 1; i <= T; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}
0