우리는 변수 번호입니다. 목표는 숫자가 먼저 감소한 다음 증가하는 [1,num] 사이의 숫자 순열 수를 찾는 것입니다. 예를 들어 num=3이면 숫자는 1,2,3입니다. 순열은 [ 3,1,2 ] 및 [2,1,3]이고 개수는 2입니다.
우리는 모든 순열에서 숫자의 감소에서 숫자의 증가로의 변화가 가장 작은 1의 위치를 기반으로 결정된다는 것을 알고 있습니다. 각 1 후에 숫자가 증가하기 시작합니다. 순열이 감소했다가 증가하려면 1이 위치 2와 num-1 사이에 있어야 합니다. [ → ...1.... → ].
1이 시작 부분에 있으면 시리즈가 완전히 증가할 것입니다[ 1.. → ], 마지막에 있으면 시리즈가 완전히 감소할 것입니다[ ... → 1 ].
num=4가 있다고 가정해 보겠습니다.
2번째 위치에 1을 배치, [ - , 1, - , - ]. 첫 번째 위치의 경우 ( 2,3,4)에서 선택할 수 있습니다. 2를 선택한다고 가정해 보겠습니다. 그러면 시퀀스는 [ 2,1,3,4]가 됩니다. 따라서 이 경우 3C1 순열이 가능합니다.
3번째 위치에 1을 배치, [ -, -, 1, - ]. 1위와 2위의 경우 3개(2,3,4) 중 2개를 선택합니다. 총 순열은 3 입니다. C2 .
따라서 총 순열은 = 3 이 됩니다. C1 + 3 C2 num=4에 대해
임의의 숫자 x에 대해 개수는 = x-1 입니다. C1 + x-1 C2 +.....+ x-1 Cc-2 =2x-1 - 이항 정리에서 2.
예를 들어 이해하자
입력 - 숫자=4
출력 − 먼저 감소한 다음 증가하는 순열의 수는 다음과 같습니다. 6
설명 − 순열은 −
[ 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
입력 - 숫자=6
출력 − 먼저 감소한 다음 증가하는 순열의 수는 − 30입니다.
설명 − 일부 순열은 −
[ 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].
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근법에서 우리는 위의 공식에서 순열을 직접 계산하기 위해 이항 정리를 사용할 것입니다. 또한 i num 을 반환하는 함수 값(long long i, long long num)을 생성합니다.
-
변수 num을 입력으로 사용합니다.
-
permutations_increase_decrease(int num) 함수는 num을 취하고 처음에는 감소한 다음 숫자 1에서 num으로 증가하는 순열의 수를 반환합니다.
-
함수 값(long long i, long long num)은 ( inum) % temp를 계산하는 데 사용됩니다. 여기서 temp=1000000007.
-
내부 permutations_increase_decrease(int num)는 temp=1000000007을 취합니다.
-
num이 1이면 순열이 불가능하므로 0을 반환합니다.
-
그렇지 않으면 세트 카운트 =(값(2, num - 1) - 2) % temp ); 공식을 사용합니다.
-
결과로 카운트를 반환합니다.
예시
#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;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of permutations that are first decreasing then increasing are: 6