https://codeiq.jp/q/2833

TriangleMaze.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		
#if DEBUG
		// sample
		Check(F(1),1);
		Check(F(2),2);
		Check(F(3),6);
		Check(F(4),42);
		Check(F(10),998593);
#endif		
		
		int N = ri();
		Console.WriteLine(F(N));
		
	}
	static long F(int n){
		// F(n+1) = F(n)*(F(n)+1) となる．
		// （入力 1 に対して n回目の操作でF(n)が得られるとすると，(n+1)回目の操作では
		//　 左下の頂点（入力 1) と 右下の頂点（入力 F(n)）の F(n)倍 を足したものが得られる)
		// ⇒ 入力の状態数が高々1000003個しかないので，鳩ノ巣原理である所から周期性を持つ
		
		if(n == 1)return 1;
		
		long mod = (long)1e6 + 3;
		long[] A = new long[(int) 1e6+3];
		Dictionary<long,int> D = new Dictionary<long,int>();
		A[1] = 1;
		int period = 0;
		int pstart = -1;
		for(int i=2;;i++){
			A[i] = A[i-1]*(A[i-1]+1)%mod;
			if(i == n) return A[i];
			
			if(!D.ContainsKey(A[i])){
				D.Add(A[i],i);
				continue;
			}
			// periodic mode start
			pstart = D[A[i]];
			period = i - D[A[i]];
			break;
		}
		
		n -= pstart;
		n %= period;
		return A[pstart + n];
	}
	
	static bool Check(long input, long ans){
		Console.Write(input==ans?"OK":"NG");
		if(input!=ans){
			Console.Write(": input={0},ans={1}",input,ans);
		}
		Console.WriteLine();
		return input==ans;
	}

	static int ri(){return int.Parse(Console.ReadLine());}
}