oj.uz

답안 #9376

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9376 2014-09-28T06:00:48 Z corea Quaternion inverse (kriii2_Q) C++14
4 / 4
 748 ms 9060 KB 
#include <cstdio>
#include <tuple>
#include <cassert>
#include <vector>
#include <algorithm>

long long M;
long long inv[1000001];

using namespace std;
 
#define REP(i, n) for(int i=0; i < n; ++i)
 
int n;

struct T {
	long long value;

	T(long long v = 0) {
		value = v;
		value %= M;
		value += M;
		value %= M;
	}
	bool zero() const {
		return value % M == 0;
	}
};

T operator / (const T x, const T y) {
//	printf("> %lld %lld\n", x.value, y.value);
	if(y.value == 0) throw 0;
	return T((x.value * inv[(int)y.value]) % M);
}
T operator * (const T x, const T y) {
	long long v = x.value * y.value;
	v %= M;
	return T(v);
}
T& operator -= (T &v, const T r) {
	v.value -= r.value;
	v.value %= M;
	v.value+= M;
	v.value%= M;
	return v;
}

typedef vector<T> VD;
typedef vector< vector<T> > matrix;
 
void gauss(matrix A, VD b, VD &x) {
	int n = A.size(), m = A[0].size();
	vector<int> where(m, -1);

	for(int c=0, r=0; c<m && r<n; ++ c) {
		int pivot = r;
		for(int i = r; i < n; ++ i) {
			if(abs(A[i][c].value) > abs(A[pivot][c].value)) pivot = i;
		}
		if(A[pivot][c].zero()) continue;
		A[pivot].swap(A[r]);
		swap(b[pivot], b[r]);
		where[c] = r;
 
		REP(i, n) if(i != r) {
			T v = A[i][c] / A[r][c];
			for(int j = c; j < m; ++ j) A[i][j] -= A[r][j] * v;
			b[i] -= b[r] * v;
		}
		++ r;
	}
	x.assign(m, 0);
	REP(i, m) if(where[i] != -1) x[i] = b[where[i]] / A[where[i]][i];
}

tuple<int, int, int, int> quaternion(long long a2, long long b2, long long c2, long long d2, long long a1, long long b1, long long c1, long long d1) {
	return make_tuple(
		T(a1 * a2 - b1 * b2 - c1 * c2 - d1 * d2).value,
		T(a1 * b2 + b1 * a2 + c1 * d2 - d1 * c2).value,
		T(a1 * c2 - b1 * d2 + c1 * a2 + d1 * b2).value,
		T(a1 * d2 + b1 * c2 - c1 * b2 + d1 * a2).value
		);
}


tuple<int ,int, int, int> go(int a, int b, int c, int d) {

	matrix A(4, VD(4));
	A[0] = {a, -b, -c, -d};
	A[1] = {b, a, -d, c};
	A[2] = {c, d, a, -b};
	A[3] = {d, -c, b, a};

	VD B = VD {T(1), T(0), T(0), T(0)};
	VD x;
	
	try {
		gauss(A, B, x);

		auto it = quaternion((int)x[0].value, (int)x[1].value, (int)x[2].value, (int)x[3].value, a,b,c,d);
		if(it == make_tuple(1, 0, 0, 0)) {
			return make_tuple( (int)x[0].value, (int)x[1].value, (int)x[2]. value, (int) x[3].value );
		} else {
			return make_tuple(0, 0, 0, 0);
		}
	}
	catch(...) {
		return make_tuple(0, 0, 0, 0);
	}
}
void naive(int a, int b, int c, int d) {
	for(int x = 0; x < M; ++ x) {
		for(int y = 0; y < M; ++ y) {
			for(int z = 0; z < M; ++ z) {
				for(int w = 0; w < M; ++ w) {
					auto it = quaternion(x,y,z,w, a,b,c,d);
//					printf("? %d %d %d %d\n", get<0>(it), get<1>(it), get<2>(it), get<3>(it));
					if(it == make_tuple(1, 0, 0, 0)) {
						printf(">> %d %d %d %d\n", x, y, z, w);
						return;
					}
				}
			}
		}
	}
	printf( "0 0 0 0\n" );
}

void func(int a,int b, int c, int d ) {
	tie(a,b,c,d) = go(a,b,c,d);
	printf("%d %d %d %d\n", a, b, c, d);
}

int main() {
	scanf("%lld", &M);

	inv[1] = 1;
	for(int i = 2; i < M; ++ i) {
		inv[i] = M - ((M/i) * inv[M % i] % M);
		assert( (inv[i] * i) % M == 1 );
	}

/*
	for( int a = 0; a < M; a ++ ) {
		for( int b = 0; b < M; b ++ ) {
			for( int c = 0; c < M; c ++ ) {
				for( int d = 0; d < M; d ++ ) {
					naive(a,b,c,d);
					func(a,b,c,d);
					printf( "\n" );
				}
			}
		}
	}
	*/
	int T;
	scanf("%d", &T);

	for(int i = 0; i < T; ++ i) {
		int a, b, c, d;
		scanf("%d %d %d %d", &a, &b, &c, &d);

		tie(a,b,c,d) = go(a,b,c,d);
		printf("%d %d %d %d\n", a, b, c, d);
	}
	return 0;
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9060 KB Output is correct
2 Correct 0 ms 9060 KB Output is correct
3 Correct 4 ms 9060 KB Output is correct
4 Correct 16 ms 9060 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 576 ms 9060 KB Output is correct
2 Correct 688 ms 9060 KB Output is correct
3 Correct 696 ms 9060 KB Output is correct
4 Correct 724 ms 9060 KB Output is correct
5 Correct 696 ms 9060 KB Output is correct
6 Correct 708 ms 9060 KB Output is correct
7 Correct 704 ms 9060 KB Output is correct
8 Correct 736 ms 9060 KB Output is correct
9 Correct 728 ms 9060 KB Output is correct
10 Correct 740 ms 9060 KB Output is correct
11 Correct 736 ms 9060 KB Output is correct
12 Correct 728 ms 9060 KB Output is correct
13 Correct 744 ms 9060 KB Output is correct
14 Correct 748 ms 9060 KB Output is correct
15 Correct 728 ms 9060 KB Output is correct