题意: Given a n * n matrix A and a positive integer k, find the sum S = A + A2 + A3 + ... + Ak.
n (n ≤ 30), k (k ≤ 109) and m (m <104)
输出结果矩阵
解法:
若 n 是偶数
- Sn= a+...+an/2 + an/2+1
- + an/2+2 +...+ an/2+n/2
- =(a+...+an/2) + an/2(a+...+an/2)
- =Sn/2+ an/2Sn/2
=(1+an/2)Sn/2 等比数列二分求和取模
2) 若 n 是奇数
- Sn= a+...+a(n-1)/2 + a(n-1)/2+1
- +...
- + a(n-1)/2+(n-1)/2 + a(n-1)/2+(n-1)/2 + 1
- =S(n-1)/2
- + a(n-1)/2(a+...+a(n-1)/2)+an
- =(1+a(n-1)/2)S(n-1)/2+an
- //#include <bits/stdc++.h>
- #include <cstdio>
- #include <cstring>
- #include <cmath>
- #include <algorithm>
- #include <iostream>
- #include <algorithm>
- #include <iostream>
- #include <cstdio>
- #include <string>
- #include <cstring>
- #include <stdio.h>
- #include <queue>
- #include <stack>;
- #include <map>
- #include <set>
- #include <ctype.h>
- #include <string.h>
- #include <vector>
- #define ME(x , y) memset(x , y , sizeof(x))
- #define SF(n) scanf("%d" , &n)
- #define rep(i , n) for(int i = 0 ; i <n ; i ++)
- #define INF 0x3f3f3f3f
- #define PI acos(-1)
- using namespace std;
- typedef long long ll ;
- int n , k , mod ;
- struct node
- {
- int a[49][49];
- node(){
- memset(a , 0 , sizeof(a));
- }
- };
- node M;
- node mul(node A , node B)
- {
- node C ;
- for(int i = 0 ; i < n ; i++)
- {
- for(int j = 0 ; j < n ; j++)
- {
- for(int k = 0 ; k < n ; k++)
- {
- C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % mod ;
- }
- }
- }
- return C ;
- }
- node quickpow(node A , int t)
- {
- node ans ;
- for(int i = 0 ; i < n ; i++)
- {
- ans.a[i][i] = 1 ;
- }
- while(t)
- {
- if(t&1)
- {
- ans = mul(ans , A) ;
- }
- t>>= 1 ;
- A = mul(A , A);
- }
- return ans ;
- }
- node jia(node A , node B)
- {
- for(int i = 0 ; i <n ; i++)
- {
- for(int j = 0 ; j < n ; j++)
- {
- A.a[i][j] = (A.a[i][j] + B.a[i][j]) % mod ;
- }
- }
- return A ;
- }
- node half(node A , int k)
- {
- if(k == 1)
- return A ;
- else if(k % 2 == 0)
- {
- return mul(half(A , k/2) , jia(quickpow(A , k/2) , M));
- }
- else{
- return jia(mul(half(A , (k-1)/2) , jia(quickpow(A , (k-1)/2) , M)) , quickpow(A , k));
- }
- }
- int main()
- {
- /*#ifdef ONLINE_JUDGE
- #else
- freopen("D:/c++/in.txt", "r", stdin);
- freopen("D:/c++/out.txt", "w", stdout);
- #endif*/
- scanf("%d%d%d" , &n , &k , &mod);
- node A , B ;
- for(int i = 0 ; i < n ; i++)
- {
- M.a[i][i] = 1 ;
- for(int j = 0 ; j < n ; j++)
- {
- scanf("%d" , &A.a[i][j]);
- }
- }
- B = half(A , k);
- for(int i = 0 ; i < n ; i++)
- {
- for(int j = 0 ; j < n ; j++)
- {
- if(j == 0)
- cout << B.a[i][j] ;
- else{
- cout << " " << B.a[i][j] ;
- }
- }
- cout << endl ;
- }
- return 0 ;
- }
解法二: 等比矩阵
- |A E|
- |0 E|
- |A , E| |A^n , 1+A^1+A^2+....+A^(n-1)|
|0 , E| 的 n 次方等于 |0 , 1 |
构造一个大矩阵, 进行快速幂后, 输出右上角矩阵.
- //#include <bits/stdc++.h>
- #include <cstdio>
- #include <cstring>
- #include <cmath>
- #include <algorithm>
- #include <iostream>
- #include <algorithm>
- #include <iostream>
- #include <cstdio>
- #include <string>
- #include <cstring>
- #include <stdio.h>
- #include <queue>
- #include <stack>;
- #include <map>
- #include <set>
- #include <ctype.h>
- #include <string.h>
- #include <vector>
- #define ME(x , y) memset(x , y , sizeof(x))
- #define SF(n) scanf("%d" , &n)
- #define rep(i , n) for(int i = 0 ; i <n ; i ++)
- #define INF 0x3f3f3f3f
- #define PI acos(-1)
- using namespace std;
- typedef long long ll ;
- int n , k , mod ;
- struct node
- {
- int a[200][200];
- node(){
- memset(a , 0 , sizeof(a));
- }
- };
- node mul(node A , node B)
- {
- node C ;
- for(int i = 0 ; i < n ; i++)
- {
- for(int j = 0 ; j < n ; j++)
- {
- for(int k = 0 ; k < n ; k++)
- {
- C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % mod ;
- }
- }
- }
- return C ;
- }
- node quickpow(node A , int t)
- {
- node ans ;
- for(int i = 0 ; i < n ; i++)
- {
- ans.a[i][i] = 1 ;
- }
- while(t)
- {
- if(t&1)
- {
- ans = mul(ans , A) ;
- }
- t>>= 1 ;
- A = mul(A , A);
- }
- return ans ;
- }
- int main()
- {
- /*#ifdef ONLINE_JUDGE
- #else
- freopen("D:/c++/in.txt", "r", stdin);
- freopen("D:/c++/out.txt", "w", stdout);
- #endif*/
- node A , B;
- scanf("%d%d%d" , &n , &k , &mod);
- for(int i = 0 ; i < n ; i++)
- {
- for(int j = 0 ; j < n ; j++)
- {
- scanf("%d" , &A.a[i][j]);
- if(i == j)
- {
- A.a[i][j+n] = 1 ;
- A.a[i+n][j+n] = 1 ;
- }
- }
- }
- n *= 2 ;
- B = quickpow(A , k+1);
- for(int i = 0 ; i < n/2 ; i++)
- {
- for(int j = n/2 ; j < n ; j++)
- {
- if(i+n/2 == j) B.a[i][j]--;
- if(j == n/2)
- cout << B.a[i][j] ;
- else{
- cout << " " << B.a[i][j] ;
- }
- }
- cout << endl ;
- }
- return 0 ;
- }
来源: http://www.bubuko.com/infodetail-3366192.html