結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-03 18:23:16
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 822 ms / 4,000 ms
コード長 1,659 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,162 ms
コンパイル使用メモリ 114,312 KB
実行使用メモリ 9,928 KB
最終ジャッジ日時 2025-08-03 18:23:29
合計ジャッジ時間 11,792 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int kN = 2e5 + 1, kM = 998244353;

int n, m, q, s[kN], f[kN], inv[kN], ans[kN];
struct Query {
  int n, k, d, id;

  bool operator<(const Query x) const { return d == x.d ? k < x.k : d < x.d; }
} qe[kN];

int Pow(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, x = 1ll * x * x % kM)
    (y & 1) && (res = 1ll * res * x % kM);
  return res;
}

int C(int n, int m) {
  if (n < m)
    return 0;
  return 1ll * f[n] * inv[m] % kM * inv[n - m] % kM;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("in", "r", stdin);
  freopen("out", "w", stdout);
#endif
  cin.tie(0)->sync_with_stdio(0);
  s[0] = f[0] = 1;
  for (int i = 1, p = 1; i < kN; i++)
    p = 2ll * p % kM, s[i] = (1ll * s[i - 1] + p) % kM, f[i] = 1ll * f[i - 1] * i % kM;
  inv[kN - 1] = Pow(f[kN - 1], kM - 2);
  for (int i = kN - 1; i >= 1; i--)
    inv[i - 1] = 1ll * inv[i] * i % kM;
  cin >> q, m = ceil(2e5 / sqrt(q));
  for (int i = 1; i <= q; i++)
    cin >> qe[i].n >> qe[i].k, qe[i].n--, qe[i].k--, qe[i].id = i, qe[i].d = qe[i].n / m;
  sort(qe + 1, qe + q + 1);
  for (int i = 1, n = 0, k = 0, res = 1; i <= q; i++) {
    for (; n < qe[i].n; n++)
      res = (2ll * res % kM - C(n, k) + kM) % kM;
    for (; n > qe[i].n; n--)
      res = (1ll * res + C(n - 1, k)) % kM * inv[2] % kM;
    for (; k < qe[i].k; k++)
      res = (1ll * res + C(n, k + 1)) % kM;
    for (; k > qe[i].k; k--)
      res = (1ll * res - C(n, k) + kM) % kM;
    ans[qe[i].id] = 1ll * res * s[n] % kM;
  }
  for (int i = 1; i <= q; i++)
    cout << ans[i] << '\n';
  return 0;
}
0