NCPC2012D A Matrix Decipher
Problem D
A Matrix Decipher
Input File: pd.in
Let ZN = {0, 1, 2, …, N-2, N-1}, where N is a positive integer. An integer linear transformation under (mod N) can be defined as
f(x) = Hx, where x ∈ ZdN, and H ∈ ZNd*d
That is, x is a d-dimensional column vector and H is a d by d matrix whose elements are from ZN.
For d = 3, we have f([見1]) = [見2]*[ 見1] = H[見1], where hij ∈ZN, 1 <= i,j <= 3. The inverse integer transformation exists only if gcd(det(H), N) = 1, that is, the determinant of matrix H is relatively prime to N. This problem assumes that N = 11.
Let Ω = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, :} be the set of 11 characters represented as numbers 0,1, …, 10, respectively. A matrix encipher takes a message, a character string consisting of 12 characters from Ω = {0, 1, 2, …, 8, 9, :}, as input and ouputs an enciphered message of the same length based on applying an integer linear transformation successively on the d characters in each group from the input message string. For example, for d = 3, a message “9870::”, decomposed as two groups of 3 characters, “987” and “0::”, is enciphered as “262976” based on the transformation matrix H = [見3]. The corresponding decipher takes “262976” as input associated with the integer transformation matrix H-1 = [見4] which converts “262976” back to “9870::”. This problem asks you to design a matrix decipher H-1 based on a given matrix encipher H to decrypt an enciphered message.
見一
[x1]
[x2]
[x3]
見二
[h11 h12 h13]
[h21 h22 h23]
[h31 h32 h33]
見三
[1 1 1]
[1 2 2]
[1 2 3]
見四
[2 10 0]
[10 2 10]
[0 10 1]
輸入說明 ：
The first line of the input file always contains one integer indicating the number of test cases to come. Each of the test cases consists of d+2 lines with d = 2 or d = 3 in the first line indicating the dimension of the encipher matrix H followed by d lines of the entries of H row by row, the (d+2)-th line is the input message of 12 characters.
輸出說明 ：
The output format is similar to the input format. The first line of the ouput file contains one integer indicating the number of test cases. Each of the test cases consists of d+2 lines with d = 2 or d = 3 in the first line indicating the dimension of the decipher matrix H-1, the next d lines are the entries of H-1 row by row, and the (d+2)-th line is the decrypted message of 12 characters.
範例輸入 ：
2 2 2 1 3 26:19278694:2 3 1 1 1 1 2 2 1 2 326242669:976
範例輸出 ：
2 2 10 8 2224488::3377 2 10 0 10 2 10 0 10 19876543210::
提示 ：
測資有錯, 或者是題目打錯請通知我。
出處 ：
這題要看懂題目真的是十分困難, 首先題目要求所有答案要 mod 11, 矩陣時輸出也是, 很明顯地要求反矩陣, 但是我們一開始並不懂他的範例測資, 輸入的矩陣代輸出的字串會等於輸入的字串結果, 輸出的矩陣可以直接由輸入的矩陣推導。
怎麼算出要求的反矩陣？這裡我並沒有使用高中的公式求反矩陣, 即使只有 2*2 或者是 3*3 的矩陣, 我仍然使用高斯消去法去得解, 如果某一列要乘上一個分數去減某一列, 那麼此時會發生 / 法, 這裡只要找到分母(會產生除法的部分)在 mod 11 下的乘法反元素(/一個數字 = *一個數字的反元素)。如此一來就好做多了。
反正不會有反矩陣不存在的情況。
#include <iostream>
using namespace std;
int inv(int x, int y, int mod) {
if(y == 0) return 1;
if(y&1) return x*inv(x*x%mod, y/2, mod)%mod;
return inv(x*x%mod, y/2, mod);
}
int main() {
int t;
char s[50];
scanf("%d", &t);
printf("%4d\n", t);
while(t--) {
int n, m, i, j, k;
scanf("%d", &n);
printf("%d\n", n);
int M[3][6] = {}, tmp;
m = 2*n;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
scanf("%d", &M[i][j]);
M[i][j] = (M[i][j]%11+11)%11;
}
M[i][i+n] = 1;
}
scanf("%s", s);
for(i = 0; i < n; i++) {
int ch = -1;
for(j = i; j < n; j++)
if(M[j][i]) {
ch = j;break;
}
if(ch == -1) puts("ERROR");
for(j = 0; j < m; j++)
swap(M[ch][j], M[i][j]);
tmp = inv(M[i][i],9,11);
for(j = 0; j < m; j++) {
M[i][j] = M[i][j]*tmp;
M[i][j] = (M[i][j]%11+11)%11;
}
for(j = 0; j < n; j++) {
if(i == j) continue;
tmp = M[j][i]*inv(M[i][i],9,11);
for(k = 0; k < m; k++) {
M[j][k] = M[j][k] - M[i][k]*tmp;
M[j][k] = (M[j][k]%11+11)%11;
}
}
}
for(i = 0; i < n;i++) {
for(j = n; j < m; j++)
printf("%4d", M[i][j]);
puts("");
}
int x1, x2, x3;
for(i = 0; i < 12; i += n) {
if(n == 2) {
s[i] -= '0';
s[i+1] -= '0';
x1 = M[0][2]*s[i] + M[0][3]*s[i+1];
x2 = M[1][2]*s[i] + M[1][3]*s[i+1];
x1 %= 11, x2 %= 11;
if(x1 != 10) x1 += '0';
else x1 = ':';
if(x2 != 10) x2 += '0';
else x2 = ':';
printf("%c%c", x1, x2);
} else {
s[i] -= '0';
s[i+1] -= '0';
s[i+2] -= '0';
x1 = M[0][3]*s[i] + M[0][4]*s[i+1] + M[0][5]*s[i+2];
x2 = M[1][3]*s[i] + M[1][4]*s[i+1] + M[1][5]*s[i+2];
x3 = M[2][3]*s[i] + M[2][4]*s[i+1] + M[2][5]*s[i+2];
x1 %= 11, x2 %= 11, x3 %= 11;
if(x1 != 10) x1 += '0';
else x1 = ':';
if(x2 != 10) x2 += '0';
else x2 = ':';
if(x3 != 10) x3 += '0';
else x3 = ':';
printf("%c%c%c", x1, x2, x3);
}
}
puts("");
}
return 0;
}
/*
2
2
2 1
3 2
6:19278694:2
3
1 1 1
1 2 2
1 2 3
26242669:976
*/