結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-03 09:18:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 972 ms / 4,000 ms
コード長 1,559 bytes
コンパイル時間 772 ms
コンパイル使用メモリ 78,812 KB
実行使用メモリ 10,676 KB
最終ジャッジ日時 2025-08-03 09:18:51
合計ジャッジ時間 13,079 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#pragma GCC optimize (3)
#define mod 998244353
using namespace std;
using ll = long long;
const int maxn = 200010;
int T;
int d;
int N = 1, M = 0, c = 1;
ll res[maxn];
ll fact[maxn], ifact[maxn];
struct Q {
  int n, m;
  int id;
} q[maxn];
bool cmp (Q x, Q y) {
  if (x.n / d == y.n / d) return x.m < y.m;
  return x.n < y.n;
}
ll P (ll x, ll y) {
  if (y == 0) return 1ll;
  ll t = P (x, y >> 1);
  if (y & 1) return t * t % mod * x % mod;
  return t * t % mod;
}
ll C (ll x, ll y) {
  return fact[x] * ifact[y] % mod * ifact[x - y] % mod;
}
void Addm () {
  c = (c + C (N, ++M)) % mod;
}
void Subm () {
  c = (c - C (N, M--) + mod) % mod;
}
void Addn () {
  c = ((c * 2 % mod - C (N++, M)) % mod + mod) % mod;
}
void Subn () {
  c = (c + C (--N, M)) % mod * ifact[2] % mod;
}
int main () {
  cin.tie (0)->sync_with_stdio (false);
  fact[0] = 1;
  for (int i = 1; i <= 200000; i++) fact[i] = fact[i - 1] * i % mod;
  for (int i = 0; i <= 200000; i++) ifact[i] = P (fact[i], mod - 2);
  cin >> T;
  d = 400;
  for (int i = 1; i <= T; i++)
    cin >> q[i].n >> q[i].m, q[i].id = i;
  sort (q + 1, q + T + 1, cmp);
  for (int i = 1; i <= T; i++) {
    res[q[i].id] = (P (2, q[i].n) - 1 + mod) % mod;
    q[i].n--;
    q[i].m--;
  }  
  for (int i = 1; i <= T; i++) {
    while (N < q[i].n) Addn ();
    while (N > q[i].n) Subn ();
    while (M < q[i].m) Addm ();
    while (M > q[i].m) Subm ();
    res[q[i].id] = res[q[i].id] * c % mod;
  }
  for (int i = 1; i <= T; i++) {
    cout << res[i] << '\n';
  }
  return 0;
}
0