2008/08/07 22:12:51
SRM413-DIV2-1000
普通にメモ化するだけでいいのかなー、落とし穴でもあるんじゃなかろうか？なんて思ってたけどそんなものはなかった。
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()
覚えた。