以下の用語を定義します。

\(X = \{0, 1, \dots, N - 1\}\) を台集合と呼ぶ。また、\(A \subset 2^X\) を開集合族、\(A\) の要素を開集合と呼ぶことにする。
\(A\) が以下の条件を満たすとき、\((X, A)\) の組を位相空間と呼ぶ。

• \(\emptyset \in A\)
• \(X \in A\)
• \(x, y \in A \implies (x \cap y) \in A\)
• \(x, y \in A \implies (x \cup y) \in A\)

すでにある位相空間を組み合わせて新しい位相空間を作れないか考えると、以下の操作ができることが分かります。

台集合を増やす

\(X = \{0, 1, \dots, N - 1\}\) を台集合とする位相空間 \((X, A)\) に対し、\(N - 1\) を含む開集合に \(N\) を加えた開集合族 \(A'\) を考えると、\((X \cup \{N\}, A')\) は位相空間である。

台集合を増やすことができるので、以下が求まれば良いです。

\(dp[x] = {}\)(要素数 \(x\) の開集合族を作るために必要な台集合の大きさ)

直積

直積位相を考えると、以下の組み合わせ方を思い付きます。

\(X = \{0, 1, \dots, N - 1\}\) を台集合とする位相空間 \((X, A)\) と \(Y = \{N, N + 1, \dots, N + M - 1\}\) を台集合とする位相空間 \((Y, B)\) に対し、\(C = \{a \cup b \mid a \in A,\ b \in B\}\) とすると、\((X \cup Y, C)\) は位相空間になる。

したがって、\(dp[xy] \gets dp[x] + dp[y]\) の遷移があることが分かります。

上下に繋げる

ハッセ図を上下に繋げることを考えると、以下の組み合わせ方を思い付きます。

\(X = \{0, 1, \dots, N - 1\}\) を台集合とする位相空間 \((X, A)\) と \(Y = \{N, N + 1, \dots, N + M - 1\}\) を台集合とする位相空間 \((Y, B)\) に対し、\(C = A \cup \{X \cup b \mid b \in B\}\) とすると、\((X \cup Y, C)\) は位相空間になる。

したがって、\(dp[x + y - 1] \gets dp[x] + dp[y]\) の遷移があることが分かります。

DP を計算する

\[ \begin{cases} dp[1] = 0\\ dp[x + y - 1] \gets dp[x] + dp[y]\\ dp[xy] \gets dp[x] + dp[y]\\ \end{cases} \]

の式にしたがって DP を計算すると、\(M \le \frac{N(N+1)}{2} \implies dp[M] \le N\) が成り立っていることが分かります。あとは、この DP の復元をして、それにしたがって位相空間を構築すれば良いです。

実装例 (C++)