公式解説の定数倍の良い別解です。公式解説の内容を理解したことを前提とするため、先に公式解説をお読みください。

\(A\) に重複する要素がある場合、それらを削除しても答えには影響しません。あらかじめ \(A\) の重複する要素を削除しておくことで、\(A\) のどの要素も高々 \(1\) 度しか出現しないようにした数列を \(A' \)、その長さを \(N'\) とします。

公式解説と同様に、多項式 \(P,Q\) を

\( P = x^{A'_0 - 1} + x^{A'_1 - 1} + \dots + x^{A'_{N'} - 1}\\ Q = x^{200000 - A'_0} + x^{200000 - A'_1} + \dots + x^{200000 - A'_{N'}} \)

により定めます。求めるべき答えは \(P \times Q\) の非零な係数の項の個数に等しいです。 ところで、あらかじめ \(A'\) からは重複する要素を除いたため \(P, Q\) の各項の係数は高々 \(1\) です。また、項の総数がそれぞれ高々 \(200000\) であることも考えると、\(P \times Q\) の各項の係数は高々 \(200000\) であることがわかります。これにより、Convolutionを例えば \(\bmod 998244353\) で求めた際に元々 \(0\) ではなかった係数が \(0\) であると誤判定されることが起きなくなることがわかります。

一般に \(\bmod 998244353\) での畳み込みは convolution_ll よりも定数倍が速いため、こちらの方がより高速です。