/
dummy.test.cpp
61 lines (49 loc) · 1.44 KB
/
dummy.test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <iostream>
#include "library/polynomial/rook_polynomial.hpp"
#include "library/polynomial/formal_power_series.hpp"
#include <atcoder/modint>
using mint = atcoder::modint998244353;
namespace atcoder {
std::istream& operator>>(std::istream& in, mint &a) {
long long e; in >> e; a = e;
return in;
}
std::ostream& operator<<(std::ostream& out, const mint &a) {
out << a.val();
return out;
}
} // namespace atcoder
using fps = suisen::FormalPowerSeries<mint>;
#include <map>
fps naive(const std::vector<int> &h) {
std::map<int, fps> pd;
pd[0] = { 1 };
for (int k : h) {
std::map<int, fps> dp;
for (auto [mask, f] : pd) {
const int nxt_mask = mask ^ ((mask >> k) << k);
dp[nxt_mask] += f;
for (int pos = 0; pos < k; ++pos) if (not ((nxt_mask >> pos) & 1)) {
dp[nxt_mask | (1 << pos)] += f << 1;
}
}
pd.swap(dp);
}
fps res(h.size() + 1);
for (auto [_, f] : pd) res += f;
return res;
}
#include <cassert>
void test() {
const std::vector<int> h { 6, 2, 5, 3, 2, 4, 5, 2, 3 };
const int n = h.size();
fps f = suisen::rook_polynomial_skyline_board<fps>(h);
fps g = naive(h);
assert(f == g);
}
int main() {
test();
std::cout << "Hello World" << std::endl;
return 0;
}