結果
問題 |
No.2206 Popcount Sum 2
|
ユーザー |
![]() |
提出日時 | 2025-08-26 12:12:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,982 bytes |
コンパイル時間 | 2,176 ms |
コンパイル使用メモリ | 200,168 KB |
実行使用メモリ | 359,040 KB |
最終ジャッジ日時 | 2025-08-26 12:13:17 |
合計ジャッジ時間 | 26,890 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 WA * 17 |
ソースコード
#include <bits/stdc++.h> #define int long long using namespace std; const int MaxN = 2e5 + 10, mod = 998244353, B = 447; struct Block { vector<int> p2; vector<vector<int>> d; int f[MaxN], v[MaxN], n; int qpow(int a, int b, int res = 1) { for (int i = 1; i <= b; i <<= 1) { (b & i) && (res = res * a % mod); a = a * a % mod; } return res; } void init() { f[0] = 1; for (int i = 1; i < MaxN; ++i) { f[i] = f[i - 1] * i % mod; } v[MaxN - 1] = qpow(f[MaxN - 1], mod - 2); for (int i = MaxN - 2; i >= 0; --i) { v[i] = v[i + 1] * (i + 1) % mod; } } int g(int x, int k) { int m = k * B; return x <= m ? p2[x] : d[k][x - m] * v[m] % mod; } Block(int _n) : n(_n) { p2.resize(n + 1), p2[0] = 1, init(); for (int i = 1; i <= n; ++i) { p2[i] = (p2[i - 1] + p2[i - 1]) % mod; } int K = (n + B - 1) / B + 2; d.resize(K); for (int k = 0; k < K; ++k) { int m = k * B; if (m > n) continue; d[k].resize(n - m + 1); d[k][0] = p2[m] * f[m] % mod; for (int i = 0; i < n - m; ++i) { d[k][i + 1] = ((d[k][i] * 2 % mod - f[i + m] * v[i] % mod) % mod + mod) % mod; } } } int query(int x, int m, int a = 0, int res = 0) { m = min(m, x + 1); if (m <= 0) return 0; if (m + m > x + 1) return (p2[x] - query(x, x + 1 - m) + mod) % mod; m--, a = m / B; if (m <= a * B + B / 2) { for (int i = a * B + 1; i <= m; ++i) { res = (res + v[i] * v[x - i] % mod) % mod; } return (g(x, a) + res * f[x] % mod) % mod; } for (int i = m + 1; i <= min((a + 1) * B, x); ++i) { res + (res + v[i] * v[x - i] % mod) % mod; } return (g(x, a + 1) - res * f[x] % mod + mod) % mod; } }; int t, n, m; signed main() { Block B(2e5 + 1); for (cin >> t; t; t--) { cin >> n >> m; cout << ((B.qpow(2, n) - 1) % mod + mod) % mod * B.query(n - 1, m) % mod << '\n'; } return 0; }