ヒント

ヒント 1

まず、良い数列の構造を分析しましょう。

ヒント 2

良い数列の全要素の和は $P$ で割り切れてはなりませんが、それで十分でしょうか。

ヒント 3

どの要素も $\frac{N}{2}$ 回より多く現れなければ（かつ総和が $P$ で割り切れなければ）、良い数列であることを証明しましょう。

ヒント 4

最頻値 $x$ について考えましょう。全要素を $x^{-1} \bmod P$ 倍すると何が起こるでしょうか。

ヒント 5

数列中に $0$ でない要素 $A_1, A_2, \dots, A_K$ があるとします。ここに最大で何個の $1$ を追加しても数列は良いままでしょうか。

ヒント 6

数列中に $1$ でない要素 $A_1, A_2, \dots, A_K$ があるとき、最大で $(P - A_1) + (P-A_2) + \dots + (P-A_K) + (P-1)$ 個の $1$ を追加できます。では、どうすれば問題を解けるでしょうか。

ヒント 7

DP を書きましょう。

解法

まず、どのような場合に数列が 良い のかを把握しましょう。

全要素の和が \(P\) で割り切れるなら、明らかに良い数列ではありません。以降、全要素の和は \(P\) で割り切れないとします。

\(X\) を数列に最も多く出現する要素（の一つ）とし、その出現回数を \(M\) とします。全要素を \(X^{-1}\) 倍すると、 \(1\) が最頻値となります。

現在の数列の \(1\) より大きい要素を \(B_1, B_2, \dots, B_K\) とします。

すると、条件を満たす並べ替えが可能な必要十分条件は、\(1\) の個数が \((P - B_1) + (P - B_2) + \dots + (P - B_K) + P-1\) を超えないことです。

必要性の証明

$1$ の個数がこれより多いとします。すると、全要素の和が $P$ で割り切れないことから、$1$ の個数は $(P - B_1) + (P - B_2) + \dots + (P - B_K) + P+1$ 個以上です。よって、全要素の和は $P(K+1) + 1$ 以上です。

条件を満たすには、点 $P, 2P, \dots, (K+1)P$ を「飛び越える」必要があり、$1$ 回飛び越えるごとに $1$ より大きい要素が $1$ つ必要です。しかし、そのような要素は $K$ 個しかなく、要素 $1$ つでは高々 $1$ 回の飛び越えしか行えないため、条件を満たす並べ替えは不可能です。

十分性の証明

以下の過程によって、条件を満たすように要素を並べることが可能であることを示します。

$x$ を現時点での残りの要素のうちの最頻値の一つとし、$cur$ を現時点で並べた要素の和とする。

• $cur + x$ が $P$ で割り切れなければ、$x$ を末尾に加える。
• そうでなければ、$x$ でないような任意の要素を一つ選び、それを $y$ として $y, x$ をこの順に末尾に加える。

まず、第二の場合では、接頭辞が $p$ で割り切れることはありません（$cur + x$ が $P$ で割り切れるなら、$cur + y$ や $cur + y + x$ は割り切れません）。

では、このアルゴリズムはいつ失敗するでしょうか？それは $cur + x$ が $P$ で割り切れてかつ $x$ 以外の要素が残っていないときのみであり、このとき残りの数は全て $x$ です。

これは、$x$ が $2$ 個以上残っていることを意味することに注目します（そうでなければ、全要素の和が $P$ で割り切れてしまいます）。その他に残っている数はありません。

さらに、これは $x$ が常に最頻値であったことに注目します（もしある時点である値 $y$ が最頻値であったとすると、それ以降「$y$ の出現数 + 1」回より多く出現する値は決して現れないことが証明できます）。

したがって $x = 1$ であり、$1$ を選べるときは常に選んだ上で最後に何個かの $1$ のみが残ったことから、作られた数列は次のようなものです。

$1$ が $P-1$ 個、$B_1$、$1$ が $P - B_1$ 個、$B_2$、$1$ が $P-B_2$ 個、$\dots$、$B_K$、$1$ が $P-B_K$ 個。そしてこの時点でようやく選択肢がなくなったことから、$1$ が $1$ 個以上残っています。

すると、$1$ の個数が命題中の数を超えてしまい、矛盾が導かれました。

あとはこの知見の下で動的計画法を行うのみです。良い数列の代わりに 悪い 数列の個数を数えることにします。

総和が \(P\) で割り切れるような数列の個数は、\(N\) が奇数のとき \(\frac{(P-1)^N - (P-1)}{P}\)、偶数のとき \(\frac{(P-1)^N + (P-1)}{P}\) です。

では、第二の要件を満たさない（上に総和が \(P\) でないような）数列の個数を数えます。\(1\) の個数が多すぎるもののみを数え、その結果を \(P-1\) 倍することにします。

\(dp[cnt][sum]\) を、\(2\) 以上 \(P-1\) 以下から \(cnt\) 個の数を選んで作られた、数列中の要素 \(x\) に対する値 \(P - x\) 全ての和が \(sum\) であるような数列の個数とします。 これらの値は簡単に \(O(N^2)\) 時間で計算できます。あとは、全ての組 \((cnt, sum)\) を列挙して、それぞれについて \(1\) の個数 \(N - cnt\) が \(N - cnt \ge sum + P\) かつ \(N - cnt \neq sum \bmod P\) を満たすか判定し、満たすなら答えに \(dp[cnt][sum]\binom{N}{cnt}\) を足します。

合計計算量: \(O(N^2)\)