DP

この問題は ABC256G の弱体化版と ABC232E を組み合わせて解くことができます。

円環上のDP

人が円環状ではなく一列に並んでいた場合を考えます。このとき、端から順に数を割り当てることを考えると、隣り合う \(2\) 人に同じ数を割り当てないためには、直前の人に割り当てた数さえわかっていれば十分です。すなわち
\(\mathrm{DP}[i][x]=\) \(i\) 人目まで数を割り当てる方法のうち、\(i\) 人目に割り当てた数が \(x\) であり、\(i\) 人目まで同じ数の人が隣り合っていないものの個数
とするDPで(計算量が莫大であることを除けば)正しい答えを求めることができます。

円環状に並んでいるときは、最初の \(1\) 人の数を決め打って
\(\mathrm{DP}_k[i][x]=\) \(i\) 人目まで数を割り当てる方法のうち、\(1\) 人目に割り当てた数が \(k\) 、\(i\) 人目に割り当てた数が \(x\) であり、\(i\) 人目まで同じ数の人が隣り合っていないものの個数
とすれば、(計算量が莫大であることを除けば) \(\sum_k \sum_{x\neq k}\mathrm{DP}_k[N][x]\) として答えを求めることができます。

このように、状態がループしている問題をDPで解く場合、1箇所を決め打ってDPを進め、\(1\) 周した最後に、末尾と先頭の条件が整合的であるもののみを考慮して解くことができます。

類題：

• ABC229F
• ABC285E
• ABC256G

状態の削減

上で述べたDPでは計算量が莫大であることから実行時間制限に間に合わせることはできません。しかしよく考えると、直前の人に何の数を割り当てた数を全て区別する必要はなく、「\(1\) 人目に割り当てた数と同じであるか」の情報さえあれば答えを求められることがわかります。すなわち
\(\mathrm{DP}[i][f]=\) \(i\) 人目まで数を割り当てる方法のうち、\(i\) 人目に割り当てた数が \(1\) 人目に割り当てた数と同じで ( \(f\) ? ある:ない) ものの個数
とすることで、状態数 \(O(N)\)、遷移 \(O(1)\) となり、全体で \(O(N)\) 時間で答えを求めることができます。求める答えは \(\mathrm{DP}[N][\mathrm{false}]\) です。

類題：

• ABC232E

writer解(C)

包除原理

「人 \(i\) と人 \(i+1\) が渡された数が異なる」という \(N\) 個の条件について包除原理を考えることでもこの問題を解くことができます。

\(N\) 個の条件をうち、固定した \(k\) 個の条件を満たさず、残りの \(N-k\) 個の条件については不問であるような割り当ての個数は \(M^{\max\{1,N-k\}}\) であることから、求める答えは \(\sum _ {k=0} ^{N} (-1)^k \binom{N}{k} M ^ {\max\{1,N-k\}}\) となります。これは \(O(N)\) や\(O(N+\log\mathrm{MOD})\) 時間で求めることができます。

writer解(Python)