SRM 414 Div1 Medium InfiniteSequence2 - Area1のif(memo[i][j])

問題

i <= 0 の場合、 $A_i = 1$
i >= 1 の場合、 $A_i = A_{\lfloor i/p \rfloor -x} + A_{\lfloor i/q \rfloor -y}$

で定義される数列がある。 $\lfloor x \rfloor$ はxの床関数である。
$A_n$ を返せ。

やりかた

単純なメモ化再帰で通る。ただしすべてメモするとMLEなので100万くらいまでメモっておいてそれ以上大きい場合は、再帰を繰り返して計算するようにすると通る。

以下ソース。

ll memo[1000001];

class InfiniteSequence2 {
public:
  int _p, _q, _x, _y;
  ll rec(ll idx){
    if(idx <= 0) return 1;
    if(idx <= 1000000 && memo[idx] >= 0) return memo[idx];

    ll ret = 0;
    ret = rec(idx / _p - _x) + rec(idx / _q - _y);
    if(idx <= 1000000) memo[idx] = ret;
    return ret;
  }
  long long calc(long long n, int p, int q, int x, int y) {
    _p = p, _q = q, _x = x,  _y = y;
    Fill(memo, -1);
    for(int i = 1; i <= 1000000; i++) rec(i);
    return rec(n);
  }
};

4,5,6月は忙しくてどれだけ解けるのか。SRMも全然出られてないし(´；ω；｀)ﾌﾞﾜｯ