oj.uz

Submission #9219

# Submission time Handle Problem Language Result Execution time Memory
9219 2014-09-28T04:49:08 Z lemonsqueeze Quaternion inverse (kriii2_Q) C++
4 / 4
 424 ms 1088 KB 
#include <stdio.h>
#include <algorithm>
using namespace std;

long long M;
long long A[4][4];
long long B[4];
long long x[4];

const int n=4;

long long getpow (long long x, long long b)
{
	if (b==0) return 1;
	if (b==1) return x;

	long long res = getpow (x, b/2);
	res = (res * res) % M;

	if (b&1) return (res * x) % M;
	return res;
}

long long getinv (long long x)
{
	// x^(M-1) = 1
	// return x^(M-2)

	return getpow (x, M-2);
}

void solve ()
{
	int l = 0;

	for (int i=0; i<n; i++) {
		for (int j=l; j<n; j++) {
			if (A[j][i]) {
				for (int k=i; k<n; k++)
					swap (A[l][k], A[j][k]);
				swap (B[l], B[j]);

				break;
			}
		}

		if (A[l][i]) {
			long long inv = getinv (A[l][i]);
			for (int j=i; j<n; j++) A[l][j] = (A[l][j] * inv) % M;
			B[l] = (B[l] * inv) % M;

			for (int j=l+1; j<n; j++) {
				long long m = A[j][i];
				for (int k=i; k<n; k++)
					A[j][k] = (A[j][k] + (M-m) * A[l][k]) % M;
				B[j] = (B[j] + (M-m) * B[l]) % M;
			}

			l++;
		}
	}

	// rank = l

	for (int i=l; i<n; i++) if (B[i]) {
		for (int j=0; j<4; j++) x[j] = 0;
		return;
	}

	for (int i=0; i<n; i++)
		x[i] = 0;

	int f[4];
	for (int i=0; i<l; i++) {
		for (int j=0; j<n; j++) if (A[i][j]) {
			f[i] = j;
			break;
		}
	}

	for (int i=l-1; i>=0; i--) {
		for (int j=f[i]+1; j<n; j++)
			B[i] = (B[i] + (M-x[j]) * A[i][j]) % M;
		x[f[i]] = B[i];
	}
}

int main ()
{
	int t;
	scanf ("%lld%d", &M, &t);
	while (t--) {
		int a, b, c, d;
		scanf ("%d%d%d%d", &a, &b, &c, &d);
		A[0][0] =  a; A[0][1] = -b; A[0][2] = -c; A[0][3] = -d;
		A[1][0] =  b; A[1][1] =  a; A[1][2] = -d; A[1][3] =  c;
		A[2][0] =  c; A[2][1] =  d; A[2][2] =  a; A[2][3] = -b;
		A[3][0] =  d; A[3][1] = -c; A[3][2] =  b; A[3][3] =  a;
		B[0] = 1;
		B[1] = 0;
		B[2] = 0;
		B[3] = 0;

		for (int i=0; i<n; i++) for (int j=0; j<n; j++)
			A[i][j] = (A[i][j] + M) % M;

		solve ();
		printf ("%lld %lld %lld %lld\n", x[0], x[1], x[2], x[3]);
	}

	return 0;
}

/*
5 3
2 3 2 1
3 1 3 2
3 2 4 1
*/

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Correct 0 ms 1088 KB Output is correct
4 Correct 4 ms 1088 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 1088 KB Output is correct
2 Correct 224 ms 1088 KB Output is correct
3 Correct 260 ms 1088 KB Output is correct
4 Correct 304 ms 1088 KB Output is correct
5 Correct 292 ms 1088 KB Output is correct
6 Correct 300 ms 1088 KB Output is correct
7 Correct 312 ms 1088 KB Output is correct
8 Correct 404 ms 1088 KB Output is correct
9 Correct 384 ms 1088 KB Output is correct
10 Correct 384 ms 1088 KB Output is correct
11 Correct 412 ms 1088 KB Output is correct
12 Correct 376 ms 1088 KB Output is correct
13 Correct 424 ms 1088 KB Output is correct
14 Correct 408 ms 1088 KB Output is correct
15 Correct 368 ms 1088 KB Output is correct