在C ++中查找数组的排列
假设我们有一个由n个从1到n的数字递增的数组，我们必须找到它可以产生的排列数。
我们知道，在组合数学中，排列是一组元素的排列，因此没有元素会出现在其原始位置。答案可能非常大，因此请返回输出mod10^9+7。
因此，如果输入为3，则输出将为2，因为原始数组为[1,2,3]。两个排列为[2,3,1]和[3,1,2]。
为了解决这个问题，我们将遵循以下步骤-
m：=10^9+7
定义一个函数add()，这将需要a，b，
return（（amodm）+（bmodm））modm
定义一个函数mul()，这将需要a，b，
return（（amodm）*（bmodm））modm
从主要方法执行以下操作
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
热门推荐
3 祝福语情人节简短
5 送大三祝福语简短
10 早安朋友祝福语简短独特
11 爸妈简短婚礼祝福语大全
12 古风祝福语 唯美简短端午
13 带猫的祝福语简短
14 新郎婚礼致辞祝福语简短
15 拜年同事祝福语大全简短
16 美术分班祝福语简短精辟
17 老板祝福语简短20字
18 中秋给爸妈祝福语简短