2018年湘潭大学程序设计竞赛G又见斐波那契(矩阵…
2018-09-18 06:24:40来源:博客园 阅读 ()
题意
题目链接
Sol
直接矩阵快速幂
推出来的矩阵应该长这样
\begin{equation*}
\begin{bmatrix}
1&1&1&1&1&1\\
1 & 0&0&0&0&0\\
0 & 0&1&3&3&1\\
0 & 0&0&1&2&1\\
0 & 0&0&0&1&1\\
0 & 0&0&0&0&1\\
\end{bmatrix}^{i - 1}*
\begin{bmatrix}
F_{1}\\
F_0\\
1\\
1\\
1\\
1
\end{bmatrix}=
\begin{bmatrix}
1&1&1&1&1&1\\
1 & 0&0&0&0&0\\
0 & 0&1&3&3&1\\
0 & 0&0&1&2&1\\
0 & 0&0&0&1&1\\
0 & 0&0&0&0&1\\
\end{bmatrix}*
\begin{bmatrix}
F_{i - 1}\\
F_{i - 2}\\
i^3\\
i^2\\
i\\
1
\end{bmatrix}=
\begin{bmatrix}
F_{i}\\
F_{i - 1}\\
(i + 1)^3\\
(i + 1)^2\\
i + 1\\
1
\end{bmatrix}
\end{equation*}
#include<cstdio> #include<algorithm> #include<queue> #include<cstring> #define Pair pair<int, int> #define MP(x, y) make_pair(x, y) #define fi first #define se second #define LL long long //#define int long long using namespace std; const int mod = 1e9 + 7; inline LL read() { char c = getchar(); LL x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int T; LL N; struct Matrix { LL a[10][10], N; Matrix() { N = 6; memset(a, 0, sizeof(a)); } Matrix operator * (const Matrix &rhs) const { Matrix ans; for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) (ans.a[i][j] += (1ll * a[i][k] * rhs.a[k][j]) % mod) %= mod; return ans; } }; Matrix fp(Matrix a, LL p) { Matrix base; // printf("%d", base.a[0][1]); for(int i = 1; i <= 6; i++) base.a[i][i] = 1; while(p) { if(p & 1) base = base * a; a = a * a; p >>= 1; } return base; } const LL GG[10][10] = { {0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 3, 3, 1}, {0, 0, 0, 0, 1, 2, 1}, {0, 0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 0, 1} }; int main() { T = read(); while(T--) { N = read(); if(N == 1) {puts("1"); continue;} if(N == 2) {puts("16"); continue;} Matrix M; memcpy(M.a, GG, sizeof(M.a)); Matrix ans = fp(M, N - 2); LL out = 0; (out += ans.a[1][1] * 16) %= mod; (out += ans.a[1][2] * 1) %= mod; (out += ans.a[1][3] * 27) %= mod; (out += ans.a[1][4] * 9) %= mod; (out += ans.a[1][5] * 3) %= mod; (out += ans.a[1][6]) %= mod; printf("%lld\n", out % mod); } return 0; } /* 5 4 1 2 3 100 */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 中学生计算机程序设计【入门例1.1】 2019-11-20
- C++程序设计学习-第1章 2019-09-23
- C程序设计语言练习 第二章 2019-09-23
- C++11程序设计要点总结-模板机制详解 2019-01-05
- 第一章 程序设计入门 2018-12-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash