程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4965 Fast Matrix Calculation 矩陣快速冪

HDU 4965 Fast Matrix Calculation 矩陣快速冪

編輯：C++入門知識

HDU 4965 Fast Matrix Calculation 矩陣快速冪

題意：一個矩陣N*K的矩陣A，一個K*N的矩陣B，(4 <= N <= 1000,2 <=K <= 6)。先進行矩陣乘法C=A*B，然後進行D=C^（N*N）的冪運算，然後對D的每個數對6取模，最後求出D的所有位置數字之和。

思路：像之前那道矩陣乘法一樣，特別大的矩陣直接進行乘法在沒有小規律的幫助時是不可能直接過的（目前看即使是Strassen矩陣算法也不會加速到要求以內）題目中給的C矩陣是1000*1000的矩陣進行快速冪是一定超時的，所以我注意到了A矩陣的列數和B矩陣的行數K是不超過六的，而6*6的矩陣進行快速冪是沒問題的。D=A*B*A*B*...*A*B*A*B，可以看成D=A*(B*A*...*B*A)*B。這樣既不影響矩陣左乘和右乘的關系，又能防止行列數太大爆掉。（題裡的小細節是挺厲害的，首先爆棧的問題需要解決，然後還有矩陣的賦值運算也是O(N)的復雜度）

代碼：

#pragma comment(linker, /STACK:1024000000,1024000000)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#define eps 1e-8
#define INF 0x7fffffff
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
#define MOD 6
#define maxn 1005
#define maxm 1005
using namespace std;
struct Matrix
{
    int n,m;
    int a[maxn][maxm];
    void init()
    {
        n=m=0;
        memset(a,0,sizeof(a));
    }
    Matrix operator +(const Matrix &b) const
    {
        Matrix tmp;
        tmp.n=n;
        tmp.m=m;
        for(int i=0; i>=1;
        m.Copy(m*m);
    }
    return tmp;
}
Matrix a,b;
int main()
{
    int n,k;
    while(scanf(%d%d,&n,&k))
    {
        if(n==0&&k==0)
            break;
        a.n=n;
        a.m=k;
        for(int i=0; i