Problem 155 再び(C++)

Haskellが遅かった．
1分以上．
そこで，単純な全探索を少し工夫して，しかも，C++で実装したら，
5秒未満になった．

#include <iostream>
#include <vector>
#include <boost/rational.hpp>
#include <boost/foreach.hpp>
#define FOREACH BOOST_FOREACH
using namespace std;
typedef boost::rational<int> rat;

static const int n = 18;

int fib(int n) {
  int p = 1, q = 0;
  for (int i = 0; i < n; i++, p += q, q = p - q) ;
  return p;
}

int main(){
  vector< vector<bool> > u(fib(n) + 1, vector<bool>(fib(n) + 1));
  vector< vector<rat> > cs(n + 1, vector<rat>());
  cs[1].push_back(rat(1)); u[1][1] = true; long long c = 0;
  for (int i = 1; i <= n; c += cs[i++].size())
    for (int j = 1; j <= i / 2; j++)
      FOREACH (rat c1, cs[j]) FOREACH (rat c2, cs[i-j]) {
	rat t = c1 + c2;
	if (u[t.numerator()][t.denominator()]) continue;
	cs[i].push_back(t); cs[i].push_back(1 / t);
	u[t.numerator()][t.denominator()] = u[t.denominator()][t.numerator()] = true;
      }
  cout << c << endl;
}

boost使ってみた．
fibがでてくるのは観察から，多分正しい（少なくとも n が18以下では正しい）．
証明はまだ，ない．