Semi-Permutations

$c_i:=$ （$A_j=i$ なる $j$ の個数）とします。
また、$c_i=0$ であるような $i$ のうち、最小のものを $P$、最小から２番目のものを $Q$ とおきます。
長さが $L\ (0\le L\le N)$ であるような準順列の個数を数えます。

• $0\le L< P-1$ のとき
  • 答えは $\displaystyle (\prod_{i=1}^{L+1}c_i)\times (\sum_{i=1}^{L+1}\frac{1}{c_i})$ です。
• $P-1\le L < Q-1$ のとき
  • 答えは $\displaystyle (\prod_{i=1}^{P-1}c_i)\times (\prod_{i=P+1}^{L+1}c_i)$ です。
• $Q-1\le L$ のとき
  • 答えは $0$ です。

よって、$c_i$ の積と逆数和を持ちながら計算することでこの問題は $O(N\log N)$ で解けます。