Codeforecs 185 A. Plant

問題

正三角形を、それぞれの辺で中点を取り、それらを結んで4つの正三角形に分割する、
という操作をn回繰り返す。

その後で、上向きの正三角形はいくつあるか、mod 10^9 + 7で答えよ。

制約条件

n≦10^12

方針

n回分割を繰り返した後の、上向きの正三角形の個数はT(2^n)個。
ただしT(m)は三角数m(m+1)/2である。

T(2^n)は2^nからなる単純な式になるので、繰り返し二乗法で求めればいい。

ソースコード

const int mod = (int)1e9 + 7;
ll modpow(ll n, ll m, ll mod){
	ll res = 1;
	for(; m; m /= 2){
		if(m & 1) res = res * n % mod;
		n = n * n % mod;
	}
	return res;
}

void run()
{
	ll n;
	cin >> n;
	if(n == 0) cout << 1 << endl;
	else cout << (modpow(2, n, mod) + 1) * modpow(2, n-1, mod) % mod << endl;
}