https://codeiq.jp/q/3130

RoomAndRoof_resub.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), 3);
		Check(F(2), 13);
		Check(F(3), 51);
		
#endif		
		
		var d = ria();
		int N = d[0];
		
		Console.WriteLine(F(N));
		
	}
	
	
	long F(int n){
		
		// P[n] = "(2 + √3)^n の整数部分6桁"である．
		// Cn = (2 + √3)^n = An + Bn √3 (An,Bn は整数） とすると，
		// An,Bnの一般項を求めることができる．
		//   An = ((2+√3)^n + (2-√3)^n) / 2
		//   Bn = ((2+√3)^n - (2-√3)^n) / 2√3
		//
		// すると，
		//   Bn √3 = ( (An + Bn√3) - (2-√3)^n ) / 2
		//   Bn √3 = An - (2-√3)^n
		//   Cn = An + Bn √3
		//      = 2*An - (2-√3)^n
		//   と書けるため，(2-√3)^n < 1 に留意すれば，結局 P[n] = 2 * An - 1 となる．
		//   従ってAnを求めればよいが，これは行列等で漸化式を計算すればよい．
		
		// naive
		long mod = 1000000;
		Mat2x2.Mod = mod;
		
		var X = Mat2x2.Unit;
		var A = new Mat2x2(2, 3, 1, 2);
		for(int i=0;i<n;i++){
			X *= A;
		}
		
		var v = new long[] {1, 0}; // 1 = 1 + 0 √3
		var res = X * v;
		return (2*res[0] - 1 + mod) % mod;
		
	}
	
	class Mat2x2{
		long[] m;
		static long mod;
		public static long Mod {
			set { mod = value; }
		}
		
		public static Mat2x2 Unit = new Mat2x2(1,0,0,1);
		
		public long this[int r, int c]{
			get{ return m[(r<<1) + c]; }
			set{ m[(r<<1) + c] = value; }
		}
		
		public Mat2x2(){
			m = new long[4];
		}
		public Mat2x2(long a, long b, long c, long d){
			m = new long[]{a, b, c, d};
		}
		
		public static Mat2x2 operator * (Mat2x2 ma, Mat2x2 mb){
			var ret = new Mat2x2();
			for(int i=0;i<2;i++){
				for(int j=0;j<2;j++){
					for(int k=0;k<2;k++){
						ret[i, j] += ma[i, k] * mb[k, j];
						if(ret[i, j] >= mod || ret[i, j] <= -mod ) ret[i, j] %= mod;
					}
					if(ret[i, j] < 0) ret[i,j] += mod;
				}
			}
			return ret;
		}
		
		public static long[] operator * (Mat2x2 ma, long[] v){
			var ret = new long[2];
			ret[0] = ma[0, 0] * v[0] + ma[0, 1] * v[1]; if(ret[0] >= mod || ret[0] <= - mod ) ret[0] %= mod;
			ret[1] = ma[1, 0] * v[0] + ma[1, 1] * v[1]; if(ret[1] >= mod || ret[1] <= - mod ) ret[1] %= mod;
			return ret;
		}
		
		public override String ToString(){
			return String.Join(" ",m);
		}
		
	}
	
	
	
	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[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
}