結果
問題 | No.2159 Filling 4x4 array |
ユーザー |
|
提出日時 | 2022-12-22 23:14:50 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,462 ms / 5,000 ms |
コード長 | 2,214 bytes |
コンパイル時間 | 2,717 ms |
コンパイル使用メモリ | 115,876 KB |
最終ジャッジ日時 | 2025-02-09 18:35:52 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 45 |
ソースコード
#include <array>#include <iostream>#include <unordered_map>#include <atcoder/modint>using mint = atcoder::modint998244353;constexpr int L = 30;constexpr int N = 4;int main() {std::array<int, N> h, w;for (auto&& e : h) std::cin >> e, e -= 4;for (auto&& e : w) std::cin >> e, e -= 4;if (std::accumulate(h.begin(), h.end(), 0LL) != std::accumulate(w.begin(), w.end(), 0LL)) {std::cout << 0 << std::endl;return 0;}constexpr int K = 4;std::array<uint32_t, 1 << (N - 1) * (N - 1)> add{};for (int s = 0; s < 1 << ((N - 1) * (N - 1)); ++s) {for (int a = 0; a < N - 1; ++a) for (int b = 0; b < N - 1; ++b) {int bit = (s >> (a * (N - 1) + b)) & 1;add[s] += bit << a * K;add[s] += bit << b * K << N * K;}}std::unordered_map<uint32_t, mint> pd{ { 0, 1 } };for (int i = 0; i < L; ++i) {uint32_t sub_lo = 0, sub_hi = 0;std::array<int, N> hb, wb;for (int a = 0; a < N; ++a) {hb[a] = ((h[a] >> i) & 1) << a * K;sub_lo += hb[a];}for (int b = 0; b < N; ++b) {wb[b] = ((w[b] >> i) & 1) << b * K;sub_hi += wb[b];}std::unordered_map<uint32_t, mint> dp;for (const auto& [k, v] : pd) {for (int s = 0; s < 1 << (N - 1) * (N - 1); ++s) {uint32_t lo = (k + add[s]) & ((1 << N * K) - 1);uint32_t hi = (k + add[s]) >> N * K;for (int a = 0; a < N - 1; ++a) {const int b = N - 1;int bit = ((lo ^ hb[a]) >> a * K) & 1;lo += bit << a * K;hi += bit << b * K;}for (int b = 0; b < N; ++b) {const int a = N - 1;int bit = ((hi ^ wb[b]) >> b * K) & 1;lo += bit << a * K;hi += bit << b * K;}hi -= sub_hi, lo -= sub_lo;dp[((hi << N * K) | lo) >> 1] += v;}}pd.swap(dp);}std::cout << pd[0].val() << std::endl;return 0;}