結果
問題 | No.1503 Bitwise And Convolution Twisted |
ユーザー |
|
提出日時 | 2021-05-07 21:55:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 407 ms / 2,000 ms |
コード長 | 1,187 bytes |
コンパイル時間 | 878 ms |
コンパイル使用メモリ | 79,092 KB |
最終ジャッジ日時 | 2025-01-21 08:08:36 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 |
ソースコード
#include <atcoder/modint> #include <iostream> #include <algorithm> #include <vector> using namespace std; using mint = atcoder::modint998244353; mint get() { int x; cin >> x; return mint::raw(x); } void solve() { int n; cin >> n; vector<mint> xs(1 << n), ys(1 << n); generate(xs.begin(), xs.end(), [] { return get(); }); generate(ys.begin(), ys.end(), [] { return get(); }); for (int i = 1; i < (1 << n); i <<= 1) { for (int b = 0; b < (1 << n); ++b) { if (b & i) { // upper zeta on A (xs) xs[b ^ i] += xs[b]; // mobius on B (ys) ys[b] -= ys[b ^ i]; } } } vector<mint> zs(1 << n); for (int b = 0; b < (1 << n); ++b) zs[b] = xs[b] * ys[b]; for (int i = 1; i < (1 << n); i <<= 1) { for (int b = 0; b < (1 << n); ++b) { if (b & i) { // lower zeta on C (zs) zs[b] += zs[b ^ i]; } } } for (auto z : zs) cout << z.val() << " "; cout << "\n"; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; }