HDU 5015 233 Matrix（西安网络赛I题）

本文主要是介绍HDU 5015 233 Matrix（西安网络赛I题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU 5015 233 Matrix

题目链接

思路：矩阵快速幂，观察没一列，第一个和为左边加最上面，第二个可以拆为左边2个加最上面，第三个可以拆为为左边3个加最上面，这样其实只要把每一列和每一列右边那列的233构造出一个矩阵，进行矩阵快速幂即可

代码：

#include <cstdio>
#include <cstring>typedef long long ll;
const int N = 15;
const int MOD = 10000007;int n, m;struct mat {ll v[N][N];mat() {memset(v, 0, sizeof(v));}mat operator * (mat c) {mat ans;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)for (int k = 0; k < n; k++)ans.v[i][j] = (ans.v[i][j] + v[i][k] * c.v[k][j] % MOD) % MOD;return ans;}
};mat pow_mod(mat x, int k) {mat ans;for (int i = 0; i < n; i++)ans.v[i][i] = 1;while (k) {if (k&1) ans = ans * x;x = x * x;k >>= 1;}return ans;
}int main() {while (~scanf("%d%d", &n, &m)) {mat A;A.v[0][0] = 1;A.v[1][0] = 1; A.v[1][1] = 10;n += 2;for (int i = 2; i < n; i++) {for (int j = 1; j <= i; j++)A.v[i][j] = 1;}A = pow_mod(A, m);ll ans = 0;ll tmp[N];tmp[0] = 3; tmp[1] = 233;for (int i = 2; i < n; i++)scanf("%I64d", &tmp[i]);for (int i = 0; i < n; i++)ans = (ans + tmp[i] * A.v[n - 1][i] % MOD) % MOD;printf("%I64d\n", ans);}return 0;
}

这篇关于HDU 5015 233 Matrix（西安网络赛I题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---