矩阵快速幂+取模运算模板

2019-04-13 17:37发布

站内文章 / 模拟电子
10100 0 1316
#include #include #include #include #include #include #include using namespace std; typedef long long ll; const int mod = 9973; const int maxn = 2000; //矩阵快速幂： int n; ll k; struct Node { int a[13][13]; }m; void muti(Node x, Node y,Node &z) {//引用是为了保证值最后传回给 A.a memset(z.a, 0, sizeof(z.a)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { z.a[i][j]+= (x.a[i][k] * y.a[k][j])%mod; z.a[i][j] %= mod; } } } } void quickpow(Node &x, ll k) { Node ans=x, base = x; while (k) { if (k & 1 == 1) muti(ans, base, ans); muti(base, base, base); k >>= 1; } x = ans; } int main() { int t; cin >> t; while (t--) { cin >> n >> k; for (int i = 1; i <= n; i++)//初始化 for (int j = 1; j <= n; j++) cin >> m.a[i][j]; Node A = m; quickpow(A, k - 1);//把矩阵和幂扔进去,要不然会多算一次 m = A; ll tr = 0; for (int i = 1; i <=n; i++) tr += m.a[i][i]; cout << tr%mod << endl; } return 0; }  

热门文章