NCPC2012D A Matrix Decipher＠Morris' Blog｜PChome Online 個人新聞台

2012-10-20 23:48:38| 人氣264| 回應0 | 上一篇 | 下一篇

NCPC2012D A Matrix Decipher

推薦 0 收藏 0 轉貼0 訂閱站台

Problem D

A Matrix Decipher

Input File: pd.in

Let Z_N = {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 ∈ Z^d_N, and H ∈ Z_N^d*d

That is, x is a d-dimensional column vector and H is a d by d matrix whose elements are from Z_N.

For d = 3, we have f([見1]) = [見2]*[ 見1] = H[見1], where h_ij∈Z_N, 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.

見一

[x₁]
[x₂]
[x₃]

見二

[h₁₁ h₁₂ h₁₃]
[h₂₁ h₂₂ h₂₃]
[h₃₁ h₃₂ h₃₃]

見三
[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.

範例輸入： help

   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::

提示：

矩陣不好表示, 請多多見諒。
測資有錯, 或者是題目打錯請通知我。

出處：

NCPC2012 (管理：morris1028)

這題要看懂題目真的是十分困難, 首先題目要求所有答案要 mod 11, 矩陣時輸出也是, 很明顯地要求反矩陣, 但是我們一開始並不懂他的範例測資, 輸入的矩陣代輸出的字串會等於輸入的字串結果, 輸出的矩陣可以直接由輸入的矩陣推導。

怎麼算出要求的反矩陣？這裡我並沒有使用高中的公式求反矩陣, 即使只有 2*2 或者是 3*3 的矩陣, 我仍然使用高斯消去法去得解, 如果某一列要乘上一個分數去減某一列, 那麼此時會發生 / 法, 這裡只要找到分母(會產生除法的部分)在 mod 11 下的乘法反元素(/一個數字 = *一個數字的反元素)。如此一來就好做多了。

反正不會有反矩陣不存在的情況。

#include <stdio.h>
#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
*/

我要檢舉

#NCPC

台長： Morris

您可能對以下文章有興趣

[ZJ][背包問題+Greedy] a455. TOI2010 第四題：商品特賣問題

[ZJ][數學][代值解] b064. 3. 下界函數

[ZJ][模擬、旋轉] b125. 積木的拼疊問題（Bricks）

b066. 5. 六芒星棋遊戲：先還是後比較有利？

人氣(264) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:NCPC2012G SHA-4
此分類上一篇:NCPC2012A String Editer

回應(0)