C++ですべてのノードを接続するために重複しないエッジを配置できる方法の数をカウントするプログラム

循環的に配置されたノードの数を表す数nがあるとします。すべてのノードがエッジで接続され、エッジが互いに交差しないように、n/2個のエッジを配置できる方法の数を見つける必要があります。答えが非常に大きい場合は、結果mod 10 ^ 9+7を返します。

したがって、入力がn =4の場合、出力は2になります。これは、以下のようにグループ化できるためです-

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

• サイズ（n / 2 + 1）の配列dpを定義します

• dp [0]：=1、dp [1]：=1

• m：=10 ^ 9 + 7

• 初期化i：=2の場合、i <=n / 2の場合、更新（iを1増やします）、実行-

  • 高：=i

  • dp [i]：=0

  • 初期化j：=1の場合、j <=high / 2の場合、更新（jを1増やします）、実行-

    • dp [i]：=（dp [i] +（2 * dp [j --1] * dp [high --j]））mod m

  • 高い％2がゼロ以外の場合、-

    • dp [i]：=（dp [i] +（dp [（high-1）/ 2] * dp [（high-1）/ 2]））mod m

  • dp [i]：=dp [i] mod m

• dp [n / 2]

  を返します

例

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

#include <bits/stdc++.h>
using namespace std;
int solve(int n) {
   vector<long long> dp(n / 2 + 1);
   dp[0] = 1;
   dp[1] = 1;
   int m = 1000000007;
   for (int i = 2; i <= n / 2; i++) {
      int high = i;
      dp[i] = 0;
      for (int j = 1; j <= high / 2; j++) {
         dp[i] = (dp[i] + (2 * dp[j - 1] * dp[high - j])) % m;
      }
      if (high % 2) dp[i] = (dp[i] + (dp[(high - 1) / 2] * dp[(high - 1) / 2])) % m;
         dp[i] %= m;
   }
   return dp[n / 2];
}
main(){
   int n = 4;
   cout << solve(n);
}

入力

4

出力

2