SHARE
TWEET

矩陣快速冪

boook Nov 15th, 2019 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define mod 1000000007LL
  5.  
  6. const int maxn = 110;
  7. int n, k;
  8.  
  9. vector<vector<int>> mul(vector<vector<int>> a, vector<vector<int>> b){
  10.     vector<vector<int>> c(maxn, vector<int>(maxn));
  11.     for(int i = 0; i < n; i ++)
  12.         for(int j = 0; j < n; j ++)
  13.             for(int k = 0; k < n; k ++)
  14.                     c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
  15.     return c;
  16. }
  17.  
  18. vector<vector<int>> ppow(vector<vector<int>> a, int k){
  19.     if(k == 1) return a;
  20.     if(k % 2 == 0) return ppow(mul(a, a), k >> 1);
  21.     if(k % 2 == 1) return mul(ppow(mul(a, a), k >> 1), a);
  22. }
  23.  
  24. int32_t main(){
  25.     cin.tie(0), cout.sync_with_stdio(0);
  26.  
  27.     cin >> n >> k;
  28.    
  29.     vector<vector<int>> a(maxn, vector<int>(maxn));
  30.    
  31.     for(int i = 0; i < n; i ++)
  32.         for(int j = 0; j < n; j ++)
  33.             cin >> a[i][j];
  34.    
  35.     a = ppow(a, k);
  36.    
  37.     for(int i = 0; i < n; i ++){
  38.         for(int j = 0; j < n; j ++)
  39.             cout << a[i][j] << " ";
  40.         cout << endl;
  41.     }
  42.     return 0;
  43. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top