結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-02 16:10:48
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 892 ms / 4,000 ms
コード長 1,627 bytes
コンパイル時間 3,161 ms
コンパイル使用メモリ 172,244 KB
実行使用メモリ 9,092 KB
最終ジャッジ日時 2025-08-02 16:11:04
合計ジャッジ時間 13,551 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:13:18: warning: operator '>>' has lower precedence than '+'; '+' will be evaluated first [-Wshift-op-parentheses]
   13 | const int I2 = P + 1 >> 1;
      |                ~~^~~ ~~
main.cpp:13:18: note: place parentheses around the '+' expression to silence this warning
   13 | const int I2 = P + 1 >> 1;
      |                  ^
      |                (    )
1 warning generated.

ソースコード

diff # 

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;
const int K = 2e5, N = K + 5;
const int B = 448;
const int P = 998244353;
const int I2 = P + 1 >> 1;

int fac[N], inv[N];
int qPow(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = 1ll * res * x % P;
    x = 1ll * x * x % P, y >>= 1;
  }
  return res;
}
int Add(int x, int y) { return x + y >= P ? x + y - P : x + y; }
int Sub(int x, int y) { return x - y < 0 ? x - y + P : x - y; }
int Binom(int x, int y) { return 1ll * fac[x] * inv[y] % P * inv[x - y] % P; }

int m, id[N], ans[N];
struct node { int k, n, id; } s[N];
bool cmp(node x, node y) {
  if (id[x.k] == id[y.k]) return x.n < y.n;
  return x.k < y.k;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> m, fac[0] = 1;
  F(i, 1, K) fac[i] = 1ll * fac[i - 1] * i % P;
  F(i, 0, K) inv[i] = qPow(fac[i], P - 2);
  F(i, 1, K) id[i] = (i - 1) / B;
  F(i, 1, m) {
    cin >> s[i].n >> s[i].k, s[i].id = i;
    --s[i].n, --s[i].k;
  }
  sort(s + 1, s + m + 1, cmp);
  int k = 0, n = 0, now = 1;
  F(i, 1, m) {
    while (k > s[i].k) now = Sub(now, Binom(n, k--));
    while (n < s[i].n) now = Sub(2ll * now % P, Binom(n++, k));
    while (k < s[i].k) now = Add(now, Binom(n, ++k));
    while (n > s[i].n) now = 1ll * I2 * Add(now, Binom(--n, k)) % P;
    ans[s[i].id] = 1ll * now * Sub(qPow(2, s[i].n + 1), 1) % P;
  }
  F(i, 1, m) cout << ans[i] << "\n";
  return 0;
}
0