FZU 1683 纪念SlingShot ★(矩阵 && 求和 && 线性变换)

题目大意：已知 F（n）=3 * F（n-1）+2 * F（n-2）+7 * F（n-3），n>=3，其中F（0）=1，F（1）=3，F（2）=5，对于给定的每个n，输出F（0）+ F（1）+ …… + F（n） mod 2009。题目链接：http://acm.fzu.edu.cn/problem.php?pid=1683 矩阵加速递推求解的一道经典好题。首先由

我们可以很快的找到递推转移矩阵：

PS:上面的图中(F(n-1), F(n-2), F(n-3) ) 应改为 (F(n+1), F(n), F(n-1) ) 那么在log(n)的时间内便可求出F(n),但是求sigma(F(n))的话还不能一个一个求。我们借助这道题中的第二种线性变换的方法：S(n+1) = S(n) + F(n+1) ，并且把加到之前的转移矩阵中加一维：

这样我们便可以在log(n)时间内求出解了~~ 注：理解并记住这种重要的方法！

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MID(x,y) ((x+y)>>1)
using namespace std;
typedef long long LL;

const int MAX = 4;
struct Mat{
    int row, col;
    int mat[MAX][MAX];
};
//initialize square matrix to unit matrix
Mat unit(int n){
    Mat A;
    A.row = A.col = n;
    memset(A.mat, 0, sizeof(A.mat));
    for (int i = 0; i < n; i ++)
        A.mat[i][i] = 1;
    return A;
}
//return A*B%mod
Mat mul(Mat A, Mat B, int mod){
    Mat C;
    C.row = A.row;
    C.col = B.col;
    for (int i = 0; i < A.row; i ++){
        for (int j = 0; j < B.col; j ++){
            C.mat[i][j] = 0;
            for (int k = 0; k < A.col; k ++)
                //注意这里要保证乘法不溢出，否则还需要设计特殊的乘法模
                C.mat[i][j] += (A.mat[i][k] * B.mat[k][j]);
            if (C.mat[i][j] >= mod)
                C.mat[i][j] %= mod;
        }
    }
    return C;
};
//return A^n%mod
Mat exp_mod(Mat A, LL n, int mod){
    Mat res = unit(A.row);
    while(n){
        if (n & 1){
            res = mul(res, A, mod);
        }
        A = mul(A, A, mod);
        n >>= 1;
    }
    return res;
}
int main(){
    int mm[4][4] = {{1, 1, 0, 0}, {0, 3, 2, 7}, {0, 1, 0, 0}, {0, 0, 1, 0}};
    int mn[4] = {4, 5, 3, 1};
    LL m, n;
    scanf("%I64d", &m);
    Mat loop;
    loop.row = loop.col = 4;
    for (int j = 0; j < 4; j ++)
        for (int k = 0; k < 4; k ++)
            loop.mat[j][k] = mm[j][k];
    Mat init_loop = loop;
    Mat res;
    res.row = 4;
    res.col = 1;
    for (int j = 0; j < 4; j ++)
        res.mat[j][0] = mn[j];
    Mat init_res = res;

    for (long long i = 1; i <= m; i ++){
        scanf("%I64d", &n);
        if (n == 1){
            printf("Case %I64d: %d\n", i, 4);
            continue;
        }
        else if (n == 0){
            printf("Case %I64d: %d\n", i, 1);
            continue;
        }
        loop = init_loop;
        loop = exp_mod(loop, n-1, 2009);

        res = init_res;
        res = mul(loop, res, 2009);
        printf("Case %I64d: %d\n", i, res.mat[0][0]);
    }
	return 0;
}

举杯独醉，饮罢飞雪，茫然又一年岁。 ------AbandonZHANG