C ++で最初に減少し、次に増加する順列をカウントします

私たちは変数numです。目標は、[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だとしましょう

1を2番目の位置に配置します[-、1、-、-]。 1番目の位置については、（2,3,4）から選択できます。たとえば、2を選択すると、シーケンスは[2,1,3,4]になります。したがって、この場合は3C1順列が可能です。

1を3番目の位置に配置します[-、-、1、-]。 1番目と2番目の位置には、3つ（2、3、4）から任意の2つを選択します。順列の合計は ³ になります C ₂ 。

したがって、順列の合計は= ³ になります。 C ₁ + ³ C ₂ num=4の場合

任意のnumxの場合、カウントは= ^x-1 になります。 C ₁ + ^x-1 C ₂ + ..... + ^x-1 C _c-2 =2 _x-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].

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、二項定理を使用して、上記の式から順列を直接計算します。また、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を返します。

• それ以外の場合、カウントを設定=（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