Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define lld long long int
- using namespace std;
- lld** base(lld** a, lld** b, int x){
- lld** aux = new lld*[1];
- aux[0] = new lld[1];
- aux[0][0] = 0;
- for(int i = 0; i < x; i++)
- aux[0][0] += a[0][i] * b[i][0];
- return aux;
- }
- lld** recorta(lld** A, int y1, int x1, int y2, int x2){
- int n = y2 - y1 + 1;
- int m = x2 - x1 + 1;
- if(n == 0 || m == 0)
- return NULL;
- lld** aux = new lld*[n];
- for(int i = 0; i < n; i++)
- aux[i] = new lld[m];
- for(int i = 0; i < n; i++){
- for(int j = 0; j < m; j++){
- aux[i][j] = A[i + y1][j + x1];
- //cout << aux[i][j] << " ";
- }
- // cout << endl;
- }
- return aux;
- }
- lld **reconstruye(lld **a, lld **b, lld **c, lld **d, int n, int m){
- lld ** aux = new lld*[n];
- for(int i = 0; i < n; i++)
- aux[i] = new lld[m];
- int nMitad = (n + 1) / 2;
- int mMitad = (m + 1) / 2;
- for(int i = 0; i < nMitad; i++){
- for(int j = 0; j < mMitad; j++){
- aux[i][j] = a[i][j];
- }
- }
- for(int i = 0; i < nMitad; i++){
- for(int j = 0; j < m - mMitad; j++){
- aux[i][j + mMitad] = b[i][j];
- }
- }
- for(int i = 0; i < n - nMitad; i++){
- for(int j = 0; j < mMitad; j++){
- aux[i + nMitad][j] = c[i][j];
- }
- }
- for(int i = 0; i < n - nMitad; i++){
- for(int j = 0; j < m - mMitad; j++){
- aux[i + nMitad][j + mMitad] = d[i][j];
- }
- }
- return aux;
- }
- lld **suma(lld **a, lld **b, int n, int m){
- for(int i = 0; i < n; i++)
- for(int j = 0; j < m; j++)
- a[i][j] += b[i][j];
- return a;
- }
- lld **multi(lld** A, lld** B, int n, int p, int m){
- if(n == 0 || p == 0 || m == 0)
- return NULL;
- if(n == 1 && m == 1)
- return base(A, B, p);
- lld **a11, **a12, **a21, **a22, **b11, **b12, **b21, **b22;
- int nMitad = (n - 1) / 2;
- int mMitad = (m - 1) / 2;
- int pMitad = (p - 1) / 2;
- a11 = recorta(A, 0, 0, nMitad, pMitad);
- a12 = recorta(A, 0, pMitad + 1, nMitad, p - 1);
- a21 = recorta(A, nMitad + 1, 0, n - 1, pMitad);
- a22 = recorta(A, nMitad + 1, pMitad + 1, n - 1, p - 1);
- b11 = recorta(B, 0, 0, pMitad, mMitad);
- b12 = recorta(B, 0, mMitad + 1, pMitad, m - 1);
- b21 = recorta(B, pMitad + 1, 0, p - 1, mMitad);
- b22 = recorta(B, pMitad + 1, mMitad + 1, p - 1, m - 1);
- lld **C11 = suma(multi(a11, b11, nMitad + 1, pMitad + 1, mMitad + 1), multi(a12, b21, nMitad + 1, p - pMitad - 1, mMitad + 1), nMitad + 1, mMitad + 1) ;
- lld **C12 = suma(multi(a11, b12, nMitad + 1, pMitad + 1, m - mMitad - 1), multi(a12, b22, nMitad + 1, p - pMitad - 1, m - mMitad - 1), nMitad + 1, m - mMitad - 1) ;
- lld **C21 = suma(multi(a21, b11, n - nMitad - 1, pMitad + 1, mMitad + 1), multi(a22, b21, n - nMitad - 1, p - pMitad - 1, mMitad + 1), n - nMitad - 1, mMitad + 1) ;
- lld **C22 = suma(multi(a21, b12, n - nMitad - 1, pMitad + 1, m - mMitad - 1), multi(a22, b22, n - nMitad - 1, p - pMitad - 1, m - mMitad - 1), n - nMitad - 1, m - mMitad - 1) ;
- return reconstruye(C11, C12, C21, C22, n, m);
- }
- int main(){
- int n, p, m;
- cin >> n >> p >> m;
- lld **A = new lld*[n];
- for(int i = 0; i < n; i++)
- A[i] = new lld[p];
- lld **B = new lld*[p];
- for(int i = 0; i < p; i++)
- B[i] = new lld[m];
- puts("Inserte la matriz A:");
- for(int i = 0; i < n; i++)
- for(int j = 0; j < p; j++)
- cin >> A[i][j];
- puts("Inserte la matriz B:");
- for(int i = 0; i < p; i++)
- for(int j = 0; j < m; j++)
- cin >> B[i][j];
- puts("La multipilacion es:");
- lld** ans = multi(A, B, n, p, m);
- for(int i = 0; i < n; i++){
- for(int j = 0; j < m; j++){
- cout << ans[i][j] << " ";
- }
- puts("");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement