计算在C ++中先减少后增加的排列
我们是一个可变的数字。目标是找到[1，num]之间的数字排列计数，其中数字先减小然后增大。例如，如果num=3，则数字为1,2,3。排列将为[3,1,2]和[2,1,3]，计数为2。
我们知道，在每个排列中，从数量减少到数量增加的变化将基于最小的位置1来确定。每增加1，数字将开始增加。为了使排列减少然后增加，位置2和num-1之间应位于1。[→...1…。→]。
如果开始时为1，则序列将完全增加[1..→]；如果结束时，则序列将完全减小[…→1]。
假设我们有num=4
将1放置在第二个位置[-，1，-，-]。对于第一个位置，我们可以从(2,3,4)中进行选择，假设我们选择2，那么序列将为[2,1,3,4]。因此在这种情况下3C1排列是可能的。
将1放置在第三位置[-，-，1，-]。对于第一位置和第二位置，请从三个(2,3,4)中选择任意两个。总排列将为3C2。
因此，对于num=4，总置换将为=3C1+3C2
对于任何numx，根据二项式定理，计数将为=x-1C1+x-1C2+....+x-1Cc-2=2x-1-2。
让我们用例子来理解
输入-num=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
输入-num=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].
以下程序中使用的方法如下
在这种方法中，我们将利用二项式定理直接根据上述公式计算置换。另外，我们将创建一个函数值（longlongi，longlongnum），该函数值返回inum
以变量num作为输入。
函数permutations_increase_decrease（intnum）取num并返回排列的数量，排列的数量先减小然后从数字1增加到num。
函数值（longlongi，longlongnum）用于计算(inum)％temp。其中temp=1000000007。
在permutations_increase_decrease（intnum）内部，采用temp=1000000007。
如果num为1，则无法进行排列，因此返回0。
其他设置计数=（value(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