まず、\(N=1\) の場合は \(P=(0)\) が解となります。以降、\(2 \le N\) とします。

\(P_1 = 0\) でない場合、\(P_i = 0\) となる \(i\) を取ります。すると \(Q_{i-1} = Q_i\) となるため条件を満たしません。より \(P_1=0\) である必要があります。

ここで、\(N\) の偶奇で場合分けをします。

• \(N\) が奇数の場合
\(\displaystyle Q_N = \frac{N(N-1)}{2} \bmod N = 0\) であり、また \(P_1 = 0\) より \(Q_1=0\) であるため条件を満たす \(P\) は存在しません。
• \(N\) が偶数の場合
\(\displaystyle 0 \le i < \frac{N}{2}\) に対して、\(P_{2i+1} = N - 2i \pmod N,P_{2i+2}=2i+1\) とすればよいです。

以上より、本問題を \(\mathrm{O}(N)\) で解くことができます。