UVALive 5112 - Sales Prediction

封装了矩阵类
比赛做得很郁闷，为什么别人写得很长、很罗嗦的代码可以过题，而我的总是过不了呢？...

/*
 * Author: rush
 * Created Time:  2011年01月05日 星期三 19时39分08秒
 * File Name: icpc/20100105/E2.cpp
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": " << (v) << endl
using namespace std;
typedef long long LL;
const LL MOD = 1000000007LL;

#define FOR(i, n) for (int i = 1; i <= (n); ++i)
typedef vector<LL> Vec;
struct Mat {
	LL mat[10][10], n;
	Mat(int _n): n(_n) { FOR(i, n) FOR(j, n) mat[i][j] = 0; }
	Mat one() const {
		Mat ans(n);
		FOR(i, n) FOR(j, n) ans[i][j] = (i == j); 
		return ans;
	}
	LL* operator[](int x) {
		return mat[x];
	}
	Mat operator *(Mat R) {
		Mat ans(n);
		FOR(i, n) FOR(j, n) {
			ans[i][j] = 0;
			FOR(k, n) ans[i][j] = (ans[i][j] + (LL)mat[i][k] * R[k][j] % MOD) % MOD;
		}
		return ans;
	}
	Vec operator *(Vec R) {
		Vec ans(10, 0);
		FOR(i, n) {
			ans[i] = 0;
			FOR(k, n) ans[i] = (ans[i] + (LL)mat[i][k] * R[k] % MOD) % MOD;
		}
		return ans;
	}
	Mat operator +(Mat R) {
		Mat ans(n);
		FOR(i, n) FOR(j, n) ans[i][j] = ((LL)mat[i][j] + R[i][j]) % MOD;
		return ans;
	}
	Mat pow(LL k) {
		Mat ans = one(), x = *this;
		while (k) {
			if (k & 1) ans = ans * x;
			k >>= 1;
			if (k) x = x * x;
		}
		return ans;
	}
	Mat sumpow(LL k) {
		// I + M + M^2 + ... + M^k
		if (k == 0) { return one(); }
		if (k % 2 == 1) {
			Mat mid = sumpow(k / 2);
			return mid + mid * pow(k / 2 + 1);
		}
		return sumpow(k - 1) * (*this) + one();
	}
};

int T;
int N, R, K;
Vec S(10, 0), a(10, 0);

int main()
{
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d", &N, &R, &K);
		FOR(i, R) scanf("%lld", &S[i]);
		for (int i = R; i >= 1; --i) scanf("%lld", &a[i]);
		
		Mat A(R);
		FOR(i, R - 1) A[i][i + 1] = 1;
		FOR(j, R) A[R][j] = a[j];
		
		Vec C = A.pow(K - 1) * S;
		Vec D = A.pow(K).sumpow(N - 1) * C;
		printf("%lld\n", D[1]);
	}
    return 0;
}