oj.uz

답안 #8411

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
8411 2014-09-13T17:32:15 Z tncks0121 Quaternion inverse (kriii2_Q) C++
4 / 4
 396 ms 1992 KB 
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h> 
#include <time.h>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
 
ll M;
int T;

ll inv[100005];

lf fpow (ll a, ll b) {
	ll ret = 1;
	while(b > 0) {
		if(b & 1) ret = (ret * a) % M;
		a = (a * a) % M;
		b >>= 1;
	}
	return ret;
}

int main() {
	scanf("%lld%d", &M, &T);
	assert(1 <= T && T <= 100000);
	for(int i = 2; i * i <= M; i++) assert(M % i != 0);

	for(int i = 1; i <= M; i++) inv[i] = fpow(i, M-2);

	while(T--) {
		ll a, b, c, d; scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		assert(0 <= a && a < M);
		assert(0 <= b && b < M);
		assert(0 <= c && c < M);
		assert(0 <= d && d < M);

		ll T[4][4] = {
		//   a2 b2 c2 d2
			{+a, -b, -c, -d},
			{+b, +a, -d, +c},
			{+c, +d, +a, -b},
			{+d, -c, +b, +a}
		};

		vector< vector<ll> > mat(4, vector<ll>(4));
		ll ans[] = {1, 0, 0, 0};

		for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) mat[i][j] = (T[i][j]+M)%M;

		for(int i = 0; i < 4; i++) {
			for(int j = i; j < 4; j++) {
				if(mat[j][i] != 0) {
					swap(mat[i], mat[j]);
					swap(ans[i], ans[j]);
					break;
				}
			}

			{
				ll t = mat[i][i];
				for(int k = 0; k < 4; k++) mat[i][k] = (mat[i][k] * inv[t]) % M;
				ans[i] = (ans[i] * inv[t]) % M;
			}

			for(int j = 0; j < 4; j++) if(i != j && mat[j][i] != 0) {
				ll t = mat[j][i];
				for(int k = 0; k < 4; k++) {
					mat[j][k] -= (mat[i][k] * t) % M;
					if(mat[j][k] < 0) mat[j][k] += M;
				}
				ans[j] -= (ans[i] * t) % M;
				if(ans[j] < 0) ans[j] += M;
			}
		}

		bool good = true;
		for(int i = 0; i < 4; i++) {
			ll w = 0;
			for(int j = 0; j < 4; j++) w = (w + ((M+T[i][j]) * ans[j]) % M) % M;
			if((i == 0 && w != 1) || (i > 0 && w != 0)) good = false;
		}

		if(!good) memset(ans, 0, sizeof ans);
		printf("%lld %lld %lld %lld\n", ans[0], ans[1], ans[2], ans[3]);
		
	}
	return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 272 ms 1992 KB Output is correct
2 Correct 336 ms 1992 KB Output is correct
3 Correct 332 ms 1992 KB Output is correct
4 Correct 316 ms 1992 KB Output is correct
5 Correct 360 ms 1992 KB Output is correct
6 Correct 340 ms 1992 KB Output is correct
7 Correct 344 ms 1992 KB Output is correct
8 Correct 352 ms 1992 KB Output is correct
9 Correct 360 ms 1992 KB Output is correct
10 Correct 384 ms 1992 KB Output is correct
11 Correct 388 ms 1992 KB Output is correct
12 Correct 392 ms 1992 KB Output is correct
13 Correct 388 ms 1992 KB Output is correct
14 Correct 396 ms 1992 KB Output is correct
15 Correct 388 ms 1992 KB Output is correct