資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢陣列的錯位排列
假設我們有一個數組，包含從 1 到 n 的 n 個數字，並且按升序排列，我們需要找到它可以生成的錯位排列的數量。
我們知道，在組合數學中，錯位排列是指集合元素的一種排列，其中沒有元素出現在其原始位置。答案可能非常大，因此返回輸出模 10^9 + 7。
因此，如果輸入為 3，則輸出將為 2，因為原始陣列為 [1,2,3]。兩個錯位排列為 [2,3,1] 和 [3,1,2]。
為了解決這個問題，我們將遵循以下步驟 -
m := 10^9 + 7
定義一個函式 add()，它將接收 a、b，
返回 ((a mod m) + (b mod m)) mod m
定義一個函式 mul()，它將接收 a、b，
返回 ((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
更新於: 2020-11-16
291 次檢視
廣告