在C ++中查找数组的排列

假设我们有一个由n个从1到n的数字递增的数组，我们必须找到它可以产生的排列数。

我们知道，在组合数学中，排列是一组元素的排列，因此没有元素会出现在其原始位置。答案可能非常大，因此请返回输出mod 10 ^ 9 + 7。

因此，如果输入为3，则输出将为2，因为原始数组为[1,2,3]。两个排列为[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