C++で配列の混乱を見つける

1からnまでのn個の数字で構成される配列が昇順であるとすると、生成できる混乱の数を見つける必要があります。

組み合わせ数学では、混乱は集合の要素の順列であり、元の位置に要素が表示されないことを私たちは知っています。答えは非常に大きい可能性があるため、出力mod 10 ^ 9+7を返します。

したがって、入力が3の場合、元の配列は[1,2,3]であるため、出力は2になります。 2つの混乱は[2,3,1]と[3,1,2]です。

これを解決するには、次の手順に従います-

• m：=10 ^ 9 + 7

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）+（b mod m））mod m

• 関数mul（）を定義します。これにはa、b、

  が必要です。

• return（（a mod m）*（b mod m））mod m

• メインの方法から次のようにします

• ret：=0

• nが1と同じ場合、-

  • 0を返す

• nが2と同じ場合、-

  • 1を返す

• サイズ（n + 1）の配列dpを定義します

• dp [2]：=1

• 初期化i：=3の場合、i <=nの場合、更新（iを1増やします）、実行-

  • dp [i]：=mul（i-1、add（dp [i-2]、dp [i-1]））

• dp [n]

  を返します

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
lli add(lli a, lli b){
   return ((a % m) + (b % m)) % m;
}
lli mul(lli a, lli b){
   return ((a % m) * (b % m)) % m;
}
class Solution {
public:
   int findDerangement(int n) {
      int ret = 0;
      if (n == 1)
         return 0;
      if (n == 2)
         return 1;
      vector dp(n + 1);
      dp[2] = 1;
      for (int i = 3; i <= n; i++) {
         dp[i] = mul(i - 1, add(dp[i - 2], dp[i - 1]));
      }
      return dp[n];
   }
};
main(){
   Solution ob;
   cout<<(ob.findDerangement(3));
}

入力

3

出力

2