UVa11703 sqrt log sin

解法
先に計算すべき配列の要素が、どれも i より小さくなるので、順に計算できる。

#include <cstdio>
#include <cmath>

using namespace std;

#define MAX (1000001)
#define MOD (1000000)

int x[MAX];

int main() {
  
  x[0] = 1;
  for(int i=1; i<MAX; i++) {
    x[i] = (
      (x[int(i-sqrt(i))] + x[(int)log(i)]) % MOD
      + x[(int)(i*sin(i)*sin(i))]
    ) % MOD;
  }
  
  int i;
  while(scanf("%d", &i) && i >= 0) {
    printf("%d\n", x[i]);
  }
  
  return 0;
}

メモ
先に全ての数列の要素を計算しておいて、その結果を用いてクエリに対して出力することにしようと考えた。x_i を作る要素は全て i より小さいかどうか考えた。0<=sqrt(x)