bitwise 2013 04

あとで書く

問題

制約条件

方針

ソースコード

const int mod = (int)1e9 + 7;

typedef vector<vi> M;
M A;
M pw[1 << 11][6];

inline M operator*(const M & a, const M &b){
	M c(a.size(), vi(b[0].size()));
	rep(i, c.size()) rep(j, c[0].size()){
		ll s = 0;
		rep(k, a[0].size()) s += (ll)a[i][k] * b[k][j] % mod;
		c[i][j] = s % mod;
	}
	return c;
}
inline M pow(ll m){
	M res(2, vi(2));
	rep(i, 2) res[i][i] = 1;
	for(int i = 0; m; i++, m /= 1 << 11){
		if(m & (1 << 11) - 1) res = res * pw[m & (1 << 11) - 1][i];
	}
	return res;
}

int q;
ll n;


int main()
{
	M I(2, vi(2));
	A = I;
	I[0][0] = I[1][1] = 1;
	A[0][0] = 2;
	A[0][1] = A[1][0] = 1;
	
	pw[0][0] = I;
	rep(i, (1 << 11) - 1) pw[i + 1][0] = pw[i][0] * A;
	rep(i, 1 << 11) rep(j, 5){
		pw[i][j + 1] = pw[i][j];
		rep(k, 11) pw[i][j + 1] = pw[i][j + 1] * pw[i][j + 1];
	}
	
	scanf("%lld", &q);
	
	while(q--){
		scanf("%lld", &n);
		printf("%lld\n", pow(n)[1][0]);
	}
	return 0;
}