SRM413: InfiniteSequence2

(問題概要)
A_i = 1 for all i <= 0;
A_i = A_[i/p]-x + A_[i/q]-y
A_nを求めよ。(n < 10^13)

(解法)
メモ化再帰。
ただし全部をmap等でメモるとMLEでセグるので、部分的にメモる。
なんかチーター本で見たような気もする。

typedef long long ll;

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class InfiniteSequence2 {
public:
  long long calc(long long n, int p, int q, int x, int y);
};

ll memo[1000000];
int p;
int q;
int x;
int y;

ll solve(ll n){
  if(n <= 0) return 1;
  if(n < 1000000 && memo[n] != -1) return memo[n];
  ll ret = solve(n / p - x) + solve(n / q - y);
  if(n < 1000000) memo[n] = ret;
  return ret;
}

long long InfiniteSequence2::calc(long long n, int p, int q, int x, int y){
  ::p = p; ::q = q; ::x = x; ::y = y;
  memset(memo, -1, sizeof(memo));
  return solve(n);
}