首页 > 代码库 > 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题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。