poj3233 又见矩阵，不过是等比吗？

9月 14

题目大意很明了，初看是像是就等比数列前n项和，但公比是一个矩阵，能用吗？

我不知道，因为如果是类似等比数列前n项和的好像关于矩阵除法比较难写，中间涉及到逆举证神马的，直接忽略

输入的数据第一行分别是$n,k,m$

代表矩阵的是$n \times n$型，求前$k$项和，结果的每一项对$m$取模

然后就是一个$n \times n$的矩阵。

我做这题时用的是类似二分的方法做的，仔细观察可以发现

$S_k = \sum_{i=1}^{k}A_{i}=(1 + {A_{\frac{k}{2}}}) \sum_{i=1}^{\frac{k}{2}}A_i + A_k = (1 + {A_{\frac{k}{2}}})S_{\frac{k}{2}} + A_k (k为奇数)$
$S_k = \sum_{i=1}^{k}A_{i}=(1 + {A_{\frac{k}{2}}}) \sum_{i=1}^{\frac{k}{2}}A_i= (1 + {A_{\frac{k}{2}}})S_{\frac{k}{2}} (k为偶数)$

故可以用这方法直接推出答案，中间要记得对数取模，以防超int，还要注意$S_1=A$ ；

然后就是写矩阵乘法与加法部分，可直接套模板

poj3233 Matrix Power Seriesview raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n , m ;
struct matrix {//矩阵
    int a[30][30];
    void init(  )
    {//初始化
        int i ;
        memset ( a, 0 ,sizeof ( a ) ) ;
        for ( i = 0 ; i < 30 ; i ++ )
            a[i][i] = 1 ;
    }
};
void print ( matrix s )
{//打印一个矩阵
    int i , j ;
    for ( i = 0 ; i < n ; i ++ )
    {
        for ( j = 0 ; j < n ; j ++ )
        {
            if ( j )
                cout<<' ';
            cout<<s.a[i][j]%m;
        }
        cout<<endl;
    }
}
matrix matrixadd ( matrix a , matrix b )
{//矩阵加法，计算时记得要取模，避免超int
    int i , j ;
    matrix c ;
    for ( i = 0 ; i < n ; i ++ )
        for ( j = 0  ; j < n ; j ++ )
            c.a[i][j]=((a.a[i][j]+b.a[i][j])%m);
    return c ;
}
matrix matrixmul ( matrix a , matrix b )
{//矩阵乘法，计算时记得要取模，避免超int
    int i , j , k ;
    matrix c ;
    for ( i = 0 ; i < n ; i ++ )
    {
        for ( j = 0 ; j < n ; j ++ )
        {
            c.a[i][j]=0;
            for ( k = 0 ; k < n ; k ++ )
                c.a[i][j] +=((a.a[i][k]*b.a[k][j])%m) ;
            c.a[i][j] %= m ;
        }
    }
    return c ;
}
matrix mul ( matrix s , int k  )
{//矩阵的k次方，快速幂
    matrix ans ;
    ans .init () ;
    while ( k >= 1 )
    {
        if ( k & 1 )
            ans = matrixmul ( ans , s ) ;
        k = k >> 1 ;
        s = matrixmul ( s , s ) ;
    }
    return ans ;
}
matrix sum ( matrix s , int k )
{//举证前k项求和
    if ( k == 1 )
        return s ;
    matrix tmp ;//用来保存答案
    tmp.init();//初始化
    tmp = matrixadd ( tmp , mul ( s , k >> 1 ) );    //计算1+A^(k/2)
    tmp = matrixmul ( tmp , sum ( s , k >> 1 ) ) ;    //计算(1+A^(k/2))*(A + A^2 + A^3 + … + A^(k/2)  )
    if ( k&1 )//考虑是否要+A^k
        tmp = matrixadd ( tmp , mul ( s , k ) ) ;
    return tmp ;//返回前n项的值
}

int main()
{
    int k ;
    while ( cin >> n >> k >> m )
    {
        int i , j ;
        matrix s ;
        for ( i = 0 ; i < n ; i ++ )
            for ( j = 0 ; j < n ; j ++ )
                cin >> s.a[i][j] ;
        s = sum ( s , k ) ;
        print(s);    
    }
    return 0;
}