グラフィックマッチング

Problem link: https://www.acmicpc.net/problem/3644
問題の説明前に重要な事実を明らかにすると、その問題の答えの範囲は64ビットの整数をはるかに超える.
答えを計算するBigIntegerクラスは事前に作成する必要があります.
以下の説明では、BigIntegerが実装されていると仮定し、コアアルゴリズムのみを説明する.
問題はDPで解決する.C_(n)を描画し、C_(n+1)を描画します.
この場合、頂点n+1からグラフィックに追加される幹線は、下図に示すように(n, n+1)であり、(n+1, 1)である.

次に、C_(n+1)のマッチング数を計算します.
マッチングの定義により、(n, n+1)、(n+1, 1)(2回にわたってn+1)を同時に含むことはできないので、自命C_(n+1)のマッチング数は以下の3つのケースの合計となる.

Case 1)(n, n+1),(n+1, 1)すべての一致数を含まない

Case 2)(n, n+1)一致する数のみを含む

Case 3)(n+1, 1)一致する数のみを含む

Case 1)では,C_(n)に存在するマッチング数は,(n, 1)を含まないマッチング数と同じであることが分かる.
下図に示すように、(n, 1)を含まないマッチングは、(n, 1)を(n, n+1)に置き換え、(n+1, 1)に置き換えるだけでよい.(n, n+1)、(n+1, 1)はいずれも選択されていない幹線であることに注意してください.

Case 2)では,C_(n)に存在するマッチング数は,頂点nを含まないマッチング数に等しいことが分かる.
ただし、頂点C_(n)において、頂点nを含まないマッチング数は、C_(n-1)に(n-1, 1)を含まないマッチング数に等しい.
下図に示すように、(n-1, 1)を含まないマッチングは、(n-1, 1)を(n, n+1)、(n+1, 1)および(n-1, n)に置き換えるだけでよい.(n, n+1)は選択された幹線であり、(n+1, 1)、(n-1, n)は選択されていない幹線であることに注意してください.

Case 3)もCase 2と同様であり、C_(n)のマッチング数は頂点1を含まないマッチング数に等しい.
したがって,Case 2のような論理を行うことができ,ここではよく考えなければならないポイントがある.
与えられた図形は非常に特殊な環状図形であるため、頂点1を含まないか、頂点2を含まないかにかかわらず、特定の頂点が含まれていない限り、数は等しくなります.
したがって,Case 3)のマッチング数はCase 2のマッチング数に等しい.
DPに考えを移すCACHEの定義は以下の通りである.

CACHE[n][0]:C_(n)に幹線(n, 1)を含まないマッチング数

CACHE[n][1]:C_(n)に存在するマッチング数

点火式は以下の通り.

CACHE[n+1][0] = CACHE[n][0] + CACHE[n-1][1] //Case 1) + Case 3)

CACHE[n+1][1] = CACHE[n][0] + 2 * CACHE[n-1][0] //Case 1) + Case 2) + Case 3)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Number
{
private:
  string number_;

public:
  Number(void) = default;
  Number& operator=(const Number& rhs) = default;

  explicit Number(const string& number) : number_(number)
  {
  }

  const std::string& number(void) const
  {
    return number_;
  }

  Number operator+(const Number& rhs) const
  {
    string result;

    size_t length = max(number().size(), rhs.number().size());

    size_t sum;
    size_t carry = 0;
    for (size_t digit = 0; digit < length; ++digit)
    {
      char digit_a = (number().size() >= digit + 1) ? number()[number().size() - digit - 1] : '0';
      char digit_b = (rhs.number().size() >= digit + 1) ? rhs.number()[rhs.number().size() - digit - 1] : '0';

      sum = ((digit_a - '0') + (digit_b - '0') + carry) % 10;
      carry = ((digit_a - '0') + (digit_b - '0') + carry) / 10;

      result += string(1, static_cast<char>(sum + '0'));
    }

    if (carry)
    {
      result += string(1, static_cast<char>(carry + '0'));
    }

    reverse(result.begin(), result.end());
    return Number(result);
  }
};

const int kMaxN = 10000;
Number CACHE[kMaxN + 1][2];

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Preprocessing
  CACHE[3][0] = Number("3");
  CACHE[3][1] = Number("4");
  CACHE[4][0] = Number("5");
  CACHE[4][1] = Number("7");

  for (int n = 5; n <= kMaxN; ++n)
  {
    CACHE[n][0] = CACHE[n - 1][0] + CACHE[n - 2][0];
    CACHE[n][1] = CACHE[n - 1][0] + CACHE[n - 2][0] + CACHE[n - 2][0];
  }

  // Solve
  int N;
  while (cin >> N)
  {
    cout << CACHE[N][1].number() << '\n';
  }

  return 0;
}