## 【HDU-5015】233 Matrix【矩阵快速幂】

【HDU-5015】233 Matrix【矩阵快速幂】

Solution：

1.发现可以通过每一列的值推出下一列的值。

2.注意到0没有贡献于最终结果，是题设故意设计的一个坑。

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 10000007;
const int LIM = 15;
struct Matrix {
LL t[LIM][LIM];
int size;
Matrix operator * (const Matrix & m) const {
Matrix ret = {{0}, size};
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
for (int k = 0; k < size; k++) {
ret.t[i][j] = (ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD;
}
}
}
return ret;
}
};

Matrix buildBase(int size) {
Matrix ret = {{0}, size};
ret.t[size - 1][size - 1] = 1;
for (int i = size - 2; i >= 0; i--) {
ret.t[i][0] = 10;
ret.t[i][size - 1] = 1;
for (int j = 1; j <= i; j++)
ret.t[i][j] = 1;
}
return ret;
}

Matrix powMod(int pow, Matrix m) {
Matrix ret = {{0}, m.size};
for (int i = 0; i < ret.size; i++)
ret.t[i][i] = 1;
while (pow) {
if (pow & 1) ret = ret * m;
m = m * m;
pow >>= 1;
}
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
LL n, m;
LL ori[LIM];
while (cin >> n >> m) {
ori[0] = 23;
ori[n + 1] = 3;
for (int i = 1; i <= n; i++) cin >> ori[i];
if (m == 0) cout << ori[n] << "\n";
else {
Matrix trans = powMod(m, buildBase(n + 2));
LL ans = 0;
for (int i = 0; i <= n + 1; i++)
ans = (ans + trans.t[n][i] * ori[i]) % MOD;
cout << ans << "\n";
}
}
return 0;
}