aceNumber.rb

class Integer

	# 整数の桁数を返す ex. 123.digit => 3
	def digit
		self / 10 == 0 ? 1 : (self / 10).digit + 1
	end

	# 整数を下1桁、下2桁、下3桁...のように分解して配列に格納する
	# ex. 12345.partiton => [5, 45, 345, 2345, 12345]
	def partition
		self.digit == 1 ? [self] : (self % 10 ** (self.digit - 1)).partition.push(self)
	end

	# self ** xを計算し、その結果の一部(下S桁)を返す
	# 下S桁の選定条件は「pivot桁以上でかつブロックpredがtrueを返すもののうち最小のそれ」
	# ただしself ** xがそもそもpivot桁未満の場合はpredがtrueになるもので最大のものを返す
	# ex. 16.pow(4, 3){|e| (e - 1) % 3 == 0} => 5536]
	# 本来 16 ** 4 => 65536 である
	# しかし「3桁にできるだけ近いもの」ということを考えると下4桁の5536が適切になる
	def pow(x, pivot, &pred)
		return 1 if x == 0

		ans = self.pow(x / 2, pivot, &pred) ** 2
		ans *= self if x.odd?

		parts = ans.partition.select{|part| yield part}
		ans.digit <= pivot ? parts.max : parts.select{|part| part.digit > pivot}.min
	end

end

# F(n)を計算しそれを10 ** 6で割ったあまりを返す
def f(n)
	(16.pow(n, 6){|e| (e - 1) % 3 == 0} - 1) / 3 * 2 % 10 ** 6
end

n = gets.to_i
p f(n)

__END__

F(n) = AAA...A(16)
     = 10 * 16 ** 0 + 10 * 16 ** 1 + 10 * 16 ** 2 + ... + 10 * 16 ** (n - 1)
これは明らかに「初項:10 * 16 ** 0 = 10, 公比:16, 項数:n」の等比数列の和であるから
F(n) = (初項 * (公比 ** 項数 - 1)) / 公比 - 1
     = (10 * (16 ** n - 1)) / (16 - 1)
     = 2 * (16 ** n - 1) / 3

ここで問題となるのは16 ** nの処遇である
nの取る範囲を考えると 16 ** n はRubyで扱える範囲を超え、オーバーフローする可能性がある
よって 16 ** n を計算するにあたっては下S桁に抑制する必要がある
そのS桁の選定条件だが、
	1. 6以上 : 10 ** 6で割った際のあまりをもとめるため
	2. (16 ** n - 1) が3の倍数となるもの : F(n)の計算にあたっては(16 ** n - 1)を3で割るため
の2つである