CodeIQ 「トライアングル・メイズ」

問題

問題はこちらhttps://codeiq.jp/challenge/2833

コード

入力が  1 \le n \le 10^8 程度だったので埋め込みをしました。
 10^7 回程度のループなら1秒もかからず実行できるので10個埋め込みをすれば十分です。
あとは、入力 n にたいして f(n) = f(n -1) \times f(n - 1) + f(n - 1) を計算します。

#include<iostream>

int main() {
	long long umekomi[] = { 1, 962661, 542563, 812109, 276578, 851210, 574610, 185493, 203688, 638904, 342482};
	long long n;

	std::cin >> n;

	int pos = n / 10000000 ;
	n -= pos * 10000000;
	long long ans = umekomi[pos];
	if (pos == 0) n--; // スタート位置の調整
	for (int i = 0; i < n; i++) {
		ans = ans * ans + ans;
		ans %= 1000003;
	}

	std::cout << ans << std::endl;
	return 0;
}