Chúng tôi là một số biến. Mục đích là để tìm số hoán vị của các số giữa [1, num] trong đó các số đầu tiên giảm sau đó tăng lên. Ví dụ nếu num =3 thì các số là 1,2,3. Các hoán vị sẽ là [3,1,2] và [2,1,3] và số lượng là 2.
Chúng ta biết rằng trong mọi hoán vị, sự thay đổi từ giảm của số thành tăng của số sẽ được quyết định dựa trên vị trí của 1 là nhỏ nhất. Sau mỗi 1, các con số sẽ bắt đầu tăng lên. Để một hoán vị giảm và sau đó tăng, 1 phải nằm giữa vị trí 2 và num-1. [→ ... 1…. →].
Nếu 1 ở đầu thì chuỗi sẽ tăng hoàn toàn [1 .. →], nếu ở cuối thì chuỗi sẽ giảm hoàn toàn [… → 1].
Giả sử chúng ta có num =4 thì
Đặt 1 ở vị trí thứ 2, [-, 1, -, -]. Đối với vị trí đầu tiên, chúng ta có thể chọn từ (2,3,4), giả sử chúng ta chọn 2, khi đó chuỗi sẽ là [2,1,3,4]. Vì vậy, hoán vị 3C1 có thể thực hiện được trong trường hợp này.
Đặt 1 ở vị trí thứ 3, [-, -, 1, -]. Đối với vị trí thứ nhất và thứ hai, hãy chọn bất kỳ hai trong ba (2,3,4). Tổng số hoán vị sẽ là 3 C 2 .
Vì vậy, tổng số hoán vị sẽ là = 3 C 1 + 3 C 2 cho num =4
Đối với bất kỳ số x nào, số lượng sẽ là = x-1 C 1 + x-1 C 2 + ..... + x-1 C c-2 =2 x-1 - 2 từ định lý nhị thức.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - num =4
Đầu ra - Số các hoán vị lúc đầu giảm dần sau đó tăng dần là:6
Giải thích - Hoán vị sẽ -
[ 2, 1, 3, 4 ], [ 3, 1, 2, 4 ], [ 4, 1, 2, 3 ] → 1 at 2nd position [ 2, 3, 1, 4 ], [ 2, 4, 1, 3 ], [ 3, 4, 1, 2 ] → 1 at 3rd position
Đầu vào - num =6
Đầu ra - Số hoán vị đầu tiên giảm sau đó tăng dần là - 30
Giải thích - Một số Hoán vị sẽ -
[ 2, 1, 3, 4, 5, 6 ], [ 3, 1, 2, 4, 5, 6 ], [ 4, 1, 2, 3, 5, 6 ], [ 5, 1, 2, 3, 4, 6 ], [ 6, 1, 2, 3, 4, 5 ] ……[ 6, 5, 4, 3, 1, 2].
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng ta sẽ sử dụng một định lý nhị thức để tính trực tiếp các hoán vị từ công thức trên. Ngoài ra, chúng tôi sẽ tạo một giá trị hàm (dài dài i, dài dài num) trả về i num
-
Lấy biến num làm đầu vào.
-
Hàm permutations_increase_decrease (int num) nhận num và trả về số lượng các hoán vị đầu tiên giảm dần sau đó tăng từ số 1 đến num.
-
Giá trị hàm (dài dài i, dài dài num) được sử dụng để tính toán (inum)% temp. Trong đó temp =1000000007.
-
Inside permutations_increase_decrease (int num) lấy temp =1000000007.
-
Nếu num là 1 thì không thể hoán vị nên trả về 0.
-
Số bộ khác =(giá trị (2, num - 1) - 2)% temp); sử dụng công thức.
-
Kết quả là số lượt trả lại.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
long long value(long long i, long long num){
int temp = 1000000007;
if (num == 0){
return 1;
}
long long j = value(i, num / 2) % temp;
j = (j * j) % temp;
if(num & 1){
j = (j * i) % temp;
}
return j;
}
int permutations_increase_decrease(int num){
int temp = 1000000007;
if (num == 1){
return 0;
}
int count = (value(2, num - 1) - 2) % temp;
return count;
}
int main(){
int num = 4;
cout<<"Count of permutations that are first decreasing then increasing are: "<<permutations_increase_decrease(num);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of permutations that are first decreasing then increasing are: 6