首页 > 代码库 > Hdu3233Matrix Power Series矩阵

Hdu3233Matrix Power Series矩阵

前面就做过了。。。二分搞下

#include <cstdio>#include <algorithm>#include <iostream>#include <string.h>typedef long long LL;using namespace std;int n, M;struct Matrix{    int m[40][40];};Matrix Mul(Matrix a, Matrix b){    Matrix ans;    for (int i = 0; i < n;i++)    for (int j = 0; j < n; j++){        ans.m[i][j] = 0;        for (int k = 0; k < n; k++){            ans.m[i][j] += a.m[i][k] * b.m[k][j];            ans.m[i][j] %= M;        }    }    return ans;}Matrix quick(Matrix a, int b){    Matrix ans;    for (int i = 0; i < n;i++)    for (int j = 0; j < n; j++)        ans.m[i][j] = (i == j);    while (b){        if (b & 1) ans = Mul(ans, a);        a = Mul(a, a);        b >>= 1;    }    return ans;}Matrix add(Matrix a, Matrix b){    for (int i = 0; i < n;i++)    for (int j = 0; j < n; j++)        a.m[i][j] += b.m[i][j], a.m[i][j] %= M;    return a;}Matrix gao(Matrix a, int len){    if (len == 1) return a;    Matrix ans;    for (int i = 0; i < n;i++)    for (int j = 0; j < n; j++) ans.m[i][j] = 0;    Matrix t = gao(a, len >> 1);    ans = add(ans, t);    ans = add(ans, Mul(t, quick(a, (len >> 1))));    if (len & 1) return add(ans, quick(a, len));    else return ans;}int main(){    int k;    while (cin >> n >> k >> M){        Matrix ans;        for (int i = 0; i < n;i++)        for (int j = 0; j < n; j++)            scanf("%d", &ans.m[i][j]);        Matrix sum = gao(ans, k);        for (int i = 0; i < n; i++){            for (int j = 0; j < n; j++)                cout << sum.m[i][j] << " ";            cout << endl;        }    }    return 0;}

 

Hdu3233Matrix Power Series矩阵