14180. Encoded CoordinatesConstraints
Time Limit: 1 secs, Memory Limit: 256 MB
Description
You have been monitoring a terrorist cell that is planning a big attack somewhere close. The terrorists have been sending encoded coordinates to each other, and you suspect that the attack will happen at one of the locations described by these coordinates. You have intercepted the relevant communications for a series of locations you want to investigate.
Every location consists of a separate x and y coordinate, each being a non-negative integer smaller than some prime number P. Both coordinates are encoded separately using the same process. A source has given you information on the process of decoding a single coordinate. The input of this process consists of five values: A, B, C, K and N.
Central to the decoding process is a collection of three functions, defined in terms of each other and the input value K:
The values A, B and C are used to initialize these functions as follows:
The decoded coordinate is the value of F(N) mod P.
As you might have noticed, there is some crucial information missing: you need the value of H(0) to calculate G(2). While you do not have this value, you do know that the x and y coordinate use the same value for H(0). Luckily, you have managed to already obtain the x coordinates for the locations. Your colleagues have suggested that this does not give you enough information to calculate the y coordinates, but you want to prove them wrong.
Input
On the first line one positive number: the number of test cases, at most 100. After that per test case:
Output
Per test case:
one line with one integer: the calculated y coordinate. If your colleagues are right, and there is not exactly one valid y coordinate, print “UNKNOWN” on a single line instead.Sample Input2112 3 5 7 44 6 8 9 7571 6 2 5 13 4 2 5 31Sample Output7UNKNOWNProblem Source
2015年每周一赛第七场
矩阵快速幂。
#include <stdio.h>/*[ 0 1 1 0 ][F( n )][F(n + 1)][ K 0 0 1 ][G( n )] = [G(n + 1)][ 1 K 0 0 ][H( n )][H(n + 1)][ 0 0 1 0 ][H(n – 1)][H( n )]*/const int OMm[4][4] = { { 0, 1, 1, 0 }, { 'k', 0, 0, 1 }, { 1, 'k', 0, 0 }, { 0, 0, 1, 0 } };const int UMm[4][4] = { { 1, 0, 0, 0 }, { 0, 1, 0, 0 }, { 0, 0, 1, 0 }, { 0, 0, 0, 1 } };struct Matrix{int m[4][4];Matrix() {}Matrix(const int m[4][4]) {for (int i = 0; i < 4; i++)for (int j = 0; j < 4; j++)this->m[i][j] = m[i][j];}};int P, Ax, Bx, Cx, Kx, Nx, Ay, By, Cy, Ky, Ny, X;Matrix Mx, My, OM(OMm), UM(UMm);Matrix MatrixPlus(Matrix M1, Matrix M2) {Matrix A;for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {A.m[i][j] = 0;for (int k = 0; k < 4; k++) A.m[i][j] = (A.m[i][j] + M1.m[i][k] * M2.m[k][j]) % P;}}return A;}Matrix MatrixKPlus(int k) {if (k == 0) return UM;if (k & 1) return MatrixPlus(OM, MatrixKPlus(k – 1));else {Matrix TempM = MatrixKPlus(k / 2);return MatrixPlus(TempM, TempM);}}int main() {int CaseNum;scanf("%d", &CaseNum);while (CaseNum–) {scanf("%d%d%d%d%d%d%d%d%d%d%d%d", &P, &Ax, &Bx, &Cx, &Kx, &Nx, &Ay, &By, &Cy, &Ky, &Ny, &X);OM.m[1][0] = OM.m[2][1] = Kx;Mx = MatrixKPlus(Nx – 1);OM.m[1][0] = OM.m[2][1] = Ky;My = MatrixKPlus(Ny – 1);int ABCx = (Mx.m[0][0] * Ax + Mx.m[0][1] * Bx + Mx.m[0][2] * Cx) % P;int ABCy = (My.m[0][0] * Ay + My.m[0][1] * By + My.m[0][2] * Cy) % P;int Ans = -1, MaybeH0;for (MaybeH0 = 0; MaybeH0 < P; MaybeH0++) {if ((MaybeH0 * Mx.m[0][3] + ABCx) % P == X) {if (Ans == -1) {Ans = (MaybeH0 * My.m[0][3] + ABCy) % P;}else if (Ans != (MaybeH0 * My.m[0][3] + ABCy) % P) {break;}}}if (MaybeH0 == P && Ans != -1) printf("%d\n", Ans);else printf("UNKNOWN\n");}return 0;}
，含泪播种的人一定能含笑收获。
