InfiniteSequence

普通にメモ化するだけでいいのかなー、落とし穴でもあるんじゃなかろうか？なんて思ってたけどそんなものはなかった。

class InfiniteSequence {
  map<long long, long long> cache;
  long long acalc (long long n, int p, int q) {
    if (n == 0) return 1;
    if (cache.find(n) == cache.end()) {
      cache[n] = acalc(n/p, p, q) + acalc(n/q, p, q);
    }
    return cache[n];
  }
public:
  long long calc(long long n, int p, int q) {
    cache.clear();
    return acalc(n,p,q);
}
};

最初手元のテストが通らなくて悩んでいたらキャッシュをクリアーしてなかった。

cache.clear()

覚えた。