c++ - 数の配列の混乱を数える (再帰)

Question

インタビューの質問の中でこの問題に出くわしました。

数値の配列が与えられた場合、この配列で可能な混乱の総数を計算する必要があります。配列の乱れは、要素が元の場所にない順列です。配列内の数値の種類に制限はありません。重複する場合もあります。

包含と排除の原則を使用した解決策を知っています。DPを使用して、再帰的な定式化を探していました。このアプローチでは、おそらくメモ化とビットマスクが使用されます。ありがとう。

Answer 1

ウィキペディアからの混乱

どこで !n は混乱の数ですが、重複がないことを前提としています。