\(E = \{ (i, j) \, | \, 1 \leq i \lt j \leq N, i \in \mathbb{Z}, j \in \mathbb{Z} \}\) とおきます。\(S \subset E\) に対し、次の値を \(f(S)\) とおきます。

• \(N\) 頂点の無向グラフであって、\((i, j) \in S\) となる頂点 \((i, j)\) 間にのみ辺が張られたものを考える。各連結成分について頂点に対応する \(A_i\) が等しくなければならないとき、\(1 \leq A_i \leq M\) かつ \(A_i\) が \(D_i\) の倍数となるように \(A_i\) を定める方法の総数。

包除原理を用いると、答えは \( \displaystyle \sum_{S \in E} f(S) (-1)^{|S|} \) となることが分かります。

頂点集合 \(T\) に対し、\(g(T) = \displaystyle \left\lfloor \frac{M}{\mathrm{lcm}_{i \in T} D_i} \right\rfloor\) とおきます。また、\(n\) 頂点のグラフにおいて、\(\frac{n(n-1)}{2}\) 本の辺のうちいくつかを選んで全体を連結にする方法に対し、選んだ本数が偶数なら \(1\)、奇数なら \(-1\) を足し合わせたものを \(h(n)\) とおきます。

\(g(T)\) は \(O(2^N)\) で前計算することができます。\(h(n)\) については、\(h(n) = (-1)^{n - 1}(n - 1)!\) が成り立つことが次の考察から分かります。

• \(h(1) = 1\) である。
• \(n \geq 2\) のとき、連結であるという条件が無ければ辺を偶数本選ぶ方法の総数と奇数本選ぶ方法の総数は等しい。頂点 \(1\) が属する連結成分を \(T\) とおいたとき、\(T \neq \{1, \dots, n \}\) である場合を除くことを考えると、\(\{1 \dots, n\} \setminus T\) の要素数が \(2\) 以上の場合は偶数本選ぶ方法の総数と奇数本選ぶ方法の総数は等しいので無視してよく、\(T\) の要素数が \(n-1\) である \(n-1\) 通りについて除くことになるため、\(h(n) = -(n - 1)h(n - 1)\) となる。

頂点が \(k\) 個の連結成分 \(T_1, \dots, T_k\) に分かれるような辺集合 \(S\) 全てについて \( f(S) (-1)^{|S|} \) を合計した値は、以下と等しくなります。

\[\displaystyle \prod_{i = 1}^k g(T_k) h(|T_k|) \]

頂点集合 \(T\) に対し、\(T\) をいくつかの連結成分に分ける方法全てに対し上記の値を合計した値を \(\mathrm{dp}_T\) とおくと、\(\mathrm{dp}_{\{1, \dots, N\}}\) が求める値となります。

\(T\) の任意の真部分集合 \(T'\) について \(\mathrm{dp}_{T'}\) の値が分かっているとします。\(T\) に含まれる頂点 \(u\) を一つ固定し、\(u\) が属する連結成分によって場合分けすると、\(\mathrm{dp}_T\) は次のように求められます。（ただし、\(\mathrm{dp}_{\empty} = 1\) とします。）

\[\displaystyle \mathrm{dp}_T = \sum_{T' \sub T, u \in T'} g(T') h(|T'|) \times \mathrm{dp}_{T \setminus T'}\]

よって、\(\mathrm{dp}\) の計算は \(O(3^N)\) で行うことができるので、この問題を解くことができました。

実装例