假设我们有一个由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