DP (Dynamic Programming)

This problem can be solved based on the idea of ABC232E and the simpler version of ABC256G.

DP on a ring

Suppose that people are arranged on a line, instead of on a ring. If we distribute integers from the leftmost people in order, in order to avoid giving the same integer to two adjacent people, it is sufficient that we know the integer given to the last person. In other words, with the following DP:
\(\mathrm{DP}[i][x]=\) the number of ways to distribute integers to the first \(i\) people so that \(x\) is given to the \(i\)-th person and no two adjacent people in the first \(i\) people have the same integer,
the correct answer can be obtained (except that the computation cost is enormous).

If they are on a ring, we can first fix the integer given to the \(1\)-st person to define
\(\mathrm{DP}[i][x]=\) the number of ways to distribute integers to the first \(i\) people so that \(k\) and \(x\) are respectively given to the \(1\)-st and \(i\)-th people and no two adjacent people in the first \(i\) people have the same integer,
the correct answer can be obtained as \(\sum_k \sum_{x\neq k}\mathrm{DP}_k[N][x]\) (except that the computation cost is enormous).

In general, when you solve a problem on a circular space with a DP, you can solve the problem by first fixing an element, advancing the DP, and making a round, considering only those the last and first conditions are consistent.

Exercise:

• ABC229F
• ABC285E
• ABC256G

Reducing states

Since the complexity of the aforementioned DP is too enormous, it does not finish within the time limit. But on second thought, we observe that we do not need to distinguish all integers assigned to the last person, but only whether the last integer equals the one given to the first person. That is, if we define
\(\mathrm{DP}[i][f]=\) the number of ways to distribute integers to the first \(i\) so that the first and \(i\)-th people are (f ? given : not given) the same integer,
now there are \(O(N)\) states and \(O(1)\) transition cost, so that we can fill the DP table in a total of \(O(N)\) time. The sought answer is \(\mathrm{DP}[N][\mathrm{false}]\).

Exercise:

• ABC232E

writer’s solution (C)

Inclusion-exclusion principle

This problem can also be solved by applying inclusion-exclusion principle to the \(N\) conditions that “person \(i\) and person \((i+1)\) receives different integer.”

Among the \(N\) conditions, suppose that \(k\) of them are satisfied and \((N-k)\) are unknown whether it is satisfied or not. There are \(M^{\max\{1,N-k\}}\) such assignments, so the sought answer is \(\sum _ {k=0} ^{N} (-1)^k \binom{N}{k} M ^ {\max\{1,N-k\}}\). This can be found in a total of \(O(N)\) or \(O(N+\log\mathrm{MOD})\) time.

writer’s solution (Python)