oj.uz

답안 #9642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9642 2014-09-28T07:47:59 Z hodduc Quaternion inverse (kriii2_Q) C++
4 / 4
 284 ms 2648 KB 
#include<stdio.h>

long long rev[200001];
int MM, T;
long long M;
int mult(int x, int e)
{
	if(e == 1) return x;
	long long tmp = mult(x, e>>1);
	tmp = (tmp * tmp) % M;
	if (e & 1) tmp = (tmp * x) % M;
	return (int)tmp;
}

void solve(int a,int b,int c, int d)
{
		long long f[4][4] = {
			{a,(M-b)%M,(M-c)%M,(M-d)%M},
			{b,a,(M-d)%M,c},
			{c,d,a,(M-b)%M},
			{d,(M-c)%M,b,a}
		};

		long long v[4] = {1,0,0,0};
		int vis[4];
		int ord[4];

		for(int t = 0; t < 4; t++) vis[t] = 0;
		for(int col = 0; col < 4; col++)
		{
			int row;
			for(row = 0; row < 4; row++) if(vis[row] == 0 && f[row][col] != 0) break;
			if(row == 4){
				ord[col] = -1;
				continue;
			}
			
			vis[row] = 1;
			ord[col] = row;

			int i, j;
			for(i = row; i == row; i++)
			{
				long long am = f[i][col];
				for(j = 0; j < 4; j++)
					f[i][j] = f[i][j] * rev[am] % M;
				v[i] = v[i] * rev[am] % M;
			}

			for(i = 0; i < 4; i++)
			{
				if(f[i][col] == 0) continue;
				if(i == row) continue;

				long long am = f[i][col];
				for(j = 0; j < 4; j++)
					f[i][j] = (f[i][j] - f[row][j] * am + M * M) % M;
				v[i] = (v[i] - v[row] * am + M * M) % M;
			}
		}

		int ass[4];
		int a2,b2,c2,d2;

		for(int i = 0; i < 4; i++)
		{
			if(f[i][0] == 0 && f[i][1] == 0 && f[i][2] == 0 && f[i][3] == 0 && v[i] != 0)
				goto FAIL;
		}

		for(int col = 0; col < 4; col++)
		{
			if(ord[col] == -1) {
				printf("0 ");
				continue;
			}
			int row = ord[col];
			int val = v[row] * rev[f[row][col]] % M;
			printf("%d ", val);
			ass[col] = val;
		}
		printf("\n");
		return;
FAIL:
		printf("0 0 0 0\n");
		return;
}

int main()
{
	scanf("%d %d", &MM, &T);
	M = MM;
	rev[1] = 1;
	for(int i = 2; i < M; i++)
		rev[i] = mult(i, M-2);

	int a, b, c, d;
	while(T--){
		scanf("%d %d %d %d", &a, &b, &c, &d);
		solve(a,b,c,d);
	}
	return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 2648 KB Output is correct
2 Correct 208 ms 2648 KB Output is correct
3 Correct 200 ms 2648 KB Output is correct
4 Correct 220 ms 2648 KB Output is correct
5 Correct 212 ms 2648 KB Output is correct
6 Correct 208 ms 2648 KB Output is correct
7 Correct 212 ms 2648 KB Output is correct
8 Correct 236 ms 2648 KB Output is correct
9 Correct 264 ms 2648 KB Output is correct
10 Correct 252 ms 2648 KB Output is correct
11 Correct 268 ms 2648 KB Output is correct
12 Correct 268 ms 2648 KB Output is correct
13 Correct 284 ms 2648 KB Output is correct
14 Correct 280 ms 2648 KB Output is correct
15 Correct 280 ms 2648 KB Output is correct