精华内容
下载资源
问答
  • 矩阵快速幂

    2021-03-25 19:52:30
    矩阵快速幂

    Luogu - P3390 【模板】矩阵快速幂

    //Luogu P3390 矩阵快速幂 
    #include<iostream>
    #include<cstring>
    #define ll long long
    #define N 102
    const int mod = 1000000007;
    using namespace std;
    ll n, k;
    struct Matrix {
    	ll val[N][N];
    	Matrix(int op = 1) {
    		memset(val,0,sizeof(val));
    		if(op) for(int i = 1; i <= n; ++i) val[i][i] = 1;
    	}
    };
    Matrix operator * (const Matrix& x, const Matrix& y) {
    	Matrix res(0);
    	for(int k = 1; k <= n; ++k) {
    		for(int i = 1; i <= n; ++i) {
    			for(int j = 1; j <= n; ++j) {
    				res.val[i][j] = (res.val[i][j] + x.val[i][k] * y.val[k][j] % mod) % mod;
    			}
    		}
    	}
    	return res;
    }
    Matrix ksm(Matrix a,ll k) {
    	Matrix res;
    	while(k) {
    		if(k & 1) res = res * a;
    		a = a * a;
    		k >>= 1;
    	}
    	return res;
    }
    int main() {
    	Matrix a, ans;
    	cin >> n >> k;
    	for(int i = 1; i <= n; ++i) {
    		for(int j = 1; j <= n; ++j) {
    			cin >> a.val[i][j];
    		}
    	}
    	ans = ksm(a,k);
    	for(int i = 1; i <= n; ++i) {
    		for(int j = 1; j <= n; ++j) {
    			cout << ans.val[i][j] << " ";
    		}
    		cout << endl;
    	}
    	return 0;
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,077
精华内容 5,230
关键字:

矩阵快速幂