• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

快速矩阵幂

开发技术 开发技术 3小时前 2次浏览
/**
 * @Author Tianyiya H.T.W
 * @Date 2019/1/8 11:23
 */
public class Main {

    private static int[][] matrixPow(int[][] x, int n) {
        int[][] one = new int[x.length][x.length];

        for (int i = 0;i < x.length; ++ i) {
            one[i][i] = 1;
        }

        int[][] base = x;
        int[][] result = one;

        while (n > 0) {
            if ((n & 1) == 1) {
                result = multi(result, base);
            }

            base = multi(base, base);
            n >>= 1;
        }
        return result;
    }

    private static int[][] multi(int[][] a, int[][] b) {
        int ax = a.length;
        int ay = a[0].length;
        int bx = b.length;
        int by = b[0].length;
        int[][] c = new int[ax][by];

        if (ay != bx) {
            return c;
        }

        for (int i = 0;i < ax; ++ i) {
            for (int j = 0;j < by;++ j) {
                for (int k = 0;k < ay;++ k) {
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return c;
    }

    private static int pow(int x, int n) {
        int base = x;
        int result = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                result *= base;
            }
            base *= base;
            n >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] x = {{1, 1}, {1, 0}};
    }
}

  


程序员灯塔
转载请注明原文链接:快速矩阵幂
喜欢 (0)