C++での美しいアレンジメント

1からNまでのN個の整数があるとします。この配列のi番目の位置（1 <=i <=N）に次のいずれかが当てはまる場合、これらのN個の数値で完全に構成される配列として美しい配列を定義します。 −

• i番目の位置の数値はiで割ることができます。
• iはi番目の位置の数値で割り切れます。

したがって、入力が2の場合、最初の美しい配置は[1,2]であるため、結果も2になります。ここで、1番目の位置（i =1）の数値は1であり、1はi（i =1）で割り切れます。次に、2番目の位置（i =2）の数は2であり、2はi（i =2）で割り切れます。 2番目の美しい配置は[2、1]です。ここで、1番目の位置（i =1）の数は2であり、2はi（i =1）で割り切れます。次に、2番目の位置（i =2）の数値は1であり、i（i =2）は1で割り切れます。

これを解決するには、次の手順に従います-

• 訪問した配列、end、posを取得する再帰メソッドsolve（）を定義します。 posは最初は1です。
• pos =end + 1の場合、ansを1増やして、戻ります
• 範囲1から終了までのiの場合
  • iが訪問されておらず、posが0で割り切れる、またはiが0で割り切れる場合、
    • 私を訪問済みとしてマーク
    • solve（visited、end、pos + 1）
    • 私を未訪問としてマーク
• メインの方法から、次の手順を実行します-
• ans：=0、visitedという配列を作成します
• sort（visited、N、1）rを呼び出します
• 回答を返します。

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int ans;
   void solve(vector <bool>& visited, int end, int pos = 1){
      if(pos == end + 1){
         ans++;
         return;
      }
      for(int i = 1; i <= end; i++){
         if(!visited[i] && (pos % i == 0 || i % pos == 0)){
            visited[i] = true;
            solve(visited, end, pos + 1);
            visited[i] = false;
         }
      }
   }
   int countArrangement(int N) {
      ans = 0;
      vector <bool> visited(N);
      solve(visited, N);
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.countArrangement(2));
}

入力

2

出力

2