Tìm sự sắp xếp của một mảng trong C ++

Giả sử chúng ta có một mảng gồm n số từ 1 đến n theo thứ tự tăng dần, chúng ta phải tìm số lượng sắp xếp mà nó có thể tạo ra.

Chúng ta biết rằng trong toán học tổ hợp, phép sắp xếp là một hoán vị của các phần tử của một tập hợp, sao cho không phần tử nào xuất hiện ở vị trí ban đầu của nó. Câu trả lời có thể rất lớn, vì vậy hãy trả về mod đầu ra 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là 3, thì đầu ra sẽ là 2, như mảng ban đầu là [1,2,3]. Hai biến vị là [2,3,1] và [3,1,2].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

m:=10 ^ 9 + 7
Xác định một hàm add (), điều này sẽ lấy a, b,
return ((a mod m) + (b mod m)) mod m
Xác định một hàm mul (), điều này sẽ nhận a, b,
return ((a mod m) * (b mod m)) mod m
Từ phương thức chính, hãy làm như sau
ret:=0
nếu n giống 1 thì -
- trả về 0
nếu n giống 2 thì -
- trả lại 1
Xác định một mảng dp có kích thước (n + 1)
dp [2]:=1
để khởi tạo i:=3, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
- dp [i]:=mul (i - 1, add (dp [i - 2], dp [i - 1]))
trả về dp [n]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơ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));
}

Tìm sự sắp xếp của một mảng trong C ++

Ví dụ

Đầu vào

Đầu ra