本文共 2356 字，大约阅读时间需要 7 分钟。
http://acm.whu.edu.cn/land/problem/detail?problem_id=1540
一道很简单的矩阵模版题，没有解出来真是打脸...
要你求斐波那契数列的每一项的三次方的前n项和。
解题思路：
要你求的是Sn 那么Sn = Sn-1 + Fx-1 ^ 3
（三个公式准备：
斐波那契数的Fx = Fx-1 + Fx-2
立方和公式 w^3 = (x + y)^3 = x^3 + 3x^2*y + 3x*y^2 + y^3;
平方和公式w^2 = (x + y)^2 = x^2 + 2*xy + y^2；）
构造一个矩阵，第一行的有5个项，分别是 Fn^3、Fn^2*Fn-1、Fn*Fn-1^2、Fn-1^3、Sn-1。
求Fn+1^3、Fn+1^2*Fn、Fn+1*Fn^2、Fn^3、Sn的情况。
然后就是利用三个公式凑出矩阵。
（得到的矩阵就是
1 1 1 1 1
3 2 1 0 0
3 1 0 0 0
1 0 0 0 0
0 0 0 0 1）
然后看一下代码吧：
#include#include using namespace std;typedef long long ll;const int maxn = 5;const ll mod = 1000000007;struct Mat{ ll m[maxn][maxn]; void initRight() { m[0][0] = m[0][1] = m[0][2] = m[0][3] = m[0][4] = 1; m[1][0] = 3, m[1][1] = 2, m[1][2] = 1; m[2][0] = 3, m[2][1] = 1; m[3][0] = 1; m[4][4] = 1; } void initLeft() { m[0][0] = m[0][1] = m[0][2] = m[0][3] = m[0][4] = 1; } Mat() { for(int i = 0; i < maxn; i++) for(int j = 0; j < maxn; j++) m[i][j] = 0; } void zero() { for(int i = 0; i < maxn; i++) for(int j = 0; j < maxn; j++) m[i][j] = 0; } void one() { for(int i = 0; i < maxn; i++) for(int j = 0; j < maxn; j++){ m[i][j] = 0; if(i == j) m[i][j] = 1; } } Mat &operator = (const Mat &rhs) { for(int i = 0; i < maxn; i++) for(int j = 0; j < maxn; j++) m[i][j] = rhs.m[i][j]; return *this; } Mat operator * (const Mat &rhs) { Mat mat; mat.zero(); for(int i = 0; i < maxn; i++) for(int j = 0; j < maxn; j++) for(int k = 0; k < maxn; k++) mat.m[i][j] = (mat.m[i][j] + m[i][k]*rhs.m[k][j])%mod; return mat; } Mat operator ^ (const int &mi) { Mat ret, a; int b = mi; ret.one(); a = *this; while(b) { if(b & 1) ret = ret*a; a = a*a; b >>= 1; } return ret; }};int main(){// freopen("data.in", "r", stdin); int n; Mat l, r, res; while(scanf("%d", &n) != EOF && n != 0) { l.zero(); r.zero(); l.initLeft(); r.initRight(); res = l * (r^(n-1)); printf("%lld\n", res.m[0][4]); } return 0;}
转载地址：http://lbhrb.baihongyu.com/