Contest Duration: - (local time) (100 minutes) Back to Home
Official

## Ex - Distinct Multiples Editorial by en_translator

Let $$E = \{ (i, j) \, | \, 1 \leq i \lt j \leq N, i \in \mathbb{Z}, j \in \mathbb{Z} \}$$. For $$S \subset E$$, let $$f(S)$$ be the following value:

• Consider an undirected graph with $$N$$ vertices that has an edge between vertices $$(i, j9$$ only if $$(i, j) \in S$$. The value is the number of ways to determine $$A_i$$ such that $$1 \leq A_i \leq M$$, $$A_i$$ is a multiple of $$D_i$$, and for each connected component, the values of $$A_i$$ corresponding to the vertices of the component should be equal.

By the inclusion-exclusion principle, we have $$\displaystyle \sum_{S \in E} f(S) (-1)^{|S|}$$.

For a set of vertices $$T$$, let $$g(T) = \displaystyle \left\lfloor \frac{M}{\mathrm{lcm}_{i \in T} D_i} \right\rfloor$$. Also, let $$h(n)$$ be the sum of $$1$$ or $$-1$$ for each subset of $$\frac{n(n-1)}{2}$$ edges that makes entire graph connected, which takes the value $$1$$ if the number of edges of the subset is even, or $$-1$$ if odd.

$$g(T)$$ can be precomputed in a total of $$O(2^N)$$ time. For $$h(n)$$ we can see that $$h(n) = (-1)^{n - 1}(n - 1)!$$ based on the following observations:

• $$h(1) = 1$$.
• If $$n \geq 2$$, then the number of ways to choose even number of edges and odd number of edges are the same, as long as it should not necessarily be connected. Let $$T$$ be the connected component that Vertex $$1$$ belongs. We consider eliminating the cases where $$T \neq \{1, \dots, n \}$$. If the number of elements of $$T \neq \{1, \dots, n \}$$ is greater than or equal to $$2$$, then the number of ways to choose even number of edges and odd number of edges is the same, so it can be ignored; we only have to eliminate $$n-1$$ cases where the number of elements in $$T$$ is $$n-1$$, so $$h(n) = -(n - 1)h(n - 1)$$.

The sum of $$f(S) (-1)^{|S|}$$ over all set of edges $$S$$ that divides the vertices into $$k$$ connected components $$T_1, \dots, T_k$$ is equal to

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

For a set of vertices $$T$$, let us denote by $$\mathrm{dp}_T$$ the sum of the value above over all the ways to divide $$T$$ into connected components. Then the desired value is $$\mathrm{dp}_{\{1, \dots, N\}}$$.

Suppose that $$\mathrm{dp}_{T'}$$ is already known for every proper subset $$T'$$ of $$T$$. Fix a vertex $$u$$ in $$T$$ and divide into cases depending on the connected component that $$u$$ belongs; then $$\mathrm{dp}_T$$ can be found as follows (where $$\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'}$

Therefore, $$\mathrm{dp}$$ can be computed in a total of $$O(3^N)$$ time, so the problem has been solved.

Sample code

posted:
last update: