package deagif;

import java.math.BigInteger;
import java.util.Scanner;

public class HillDecrypt {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		// 秘钥矩阵
		int[][] A = {
			{ 1, 1, 0 },
			{ 2, 1, 1 },
			{ 3, 2, 2 },
		};
		A = Inverse(A);

		System.out.print("请输入密文:");
		String line = input.nextLine();

		// 将字符转换成大写
		line = line.toUpperCase();
		String[] lines = line.split("");

		int n = (int) Math.ceil(lines.length / 3.0);
		int[][][] oriMatrix = new int[n][3][1];

		// 按照ASCII码表转换数字，导入矩阵
		for (int i = 1; i <= lines.length; i++) {
			String s = lines[i - 1];

			int unicode = (int) s.charAt(0);
			unicode -= 64;

			oriMatrix[(i - 1) / 3][(i - 1) % 3][0] = unicode;
		}

		int[][][] resultMatrix = new int[n][3][1];

		// 根据秘钥作矩阵乘法
		int index = 0;
		for (int[][] rMatrix : oriMatrix) {
			int[][] outMatrix = MatrixMultiply(A, rMatrix);
			resultMatrix[index] = outMatrix;

			index++;
		}

		for (int i = 0; i < n; i++) {
			for (int k = 0; k < 3; k++) {
				int num = resultMatrix[i][k][0] % 26;
				while(num < 0) {
					num += 26;
				}
				if(num == 0) {
					if(i < n-1 || k < 2) {
						num += 26;
					}
				}
				System.out.print((char) (num+ 64));
			}
		}
	}
	
	// 计算矩阵的逆
    public static int[][] Inverse(int[][] matrix) {
        int n = matrix.length;
        int[][] augmentedMatrix = new int[n][2 * n];

        // 构建增广矩阵 [matrix | identity]
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                augmentedMatrix[i][j] = matrix[i][j];
                augmentedMatrix[i][j + n] = (i == j) ? 1 : 0; // 单位矩阵部分
            }
        }

        // 利用高斯-约当消元法进行行变换
        for (int i = 0; i < n; i++) {
            // 将主元归一化为1
            int pivot = augmentedMatrix[i][i];
            for (int j = 0; j < 2 * n; j++) {
                augmentedMatrix[i][j] /= pivot;
            }

            // 消元操作，使得第 i 列其他元素变为0
            for (int k = 0; k < n; k++) {
                if (k != i) {
                    int factor = augmentedMatrix[k][i];
                    for (int j = 0; j < 2 * n; j++) {
                        augmentedMatrix[k][j] -= factor * augmentedMatrix[i][j];
                    }
                }
            }
        }

        // 提取逆矩阵部分并返回
        int[][] inverseMatrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                inverseMatrix[i][j] = augmentedMatrix[i][j + n];
            }
        }

        return inverseMatrix;
    }

	// 矩阵的乘法运算
	public static int[][] MatrixMultiply(int[][] A, int[][] B) {
		int aR = A.length;
		int aC = A[0].length; // ==bR

		int bC = B[0].length;

		if (aC != B.length) {
			System.out.println("A的列数!=B的行数，无法相乘");
			return null;
		}

		int[][] C = new int[aR][bC];

		// 乘法运算(左行右列加和)
		for (int i = 0; i < aR; i++) {
			for (int j = 0; j < bC; j++) {
				int sum = 0;
				for (int k = 0; k < aC; k++) {
					sum += A[i][k] * B[k][j];
				}
				C[i][j] = sum;
			}
		}

		return C;
	}
}