oj.uz

답안 #21419

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
21419 2017-04-13T19:33:00 Z gs14004 Quaternion inverse (kriii2_Q) C++11
4 / 4
 316 ms 2412 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int inv[100005], mod;

vector<vector<int>> aug;
vector<int> sol;

void solve(){
	vector<int> basis[4];
	vector<int> sol2 = {0, 0, 0, 0};
	for(int i=0; i<4; i++){
		bool ok = 0;
		for(int j=0; j<4; j++){
			if(aug[i][j]){
				if(basis[j].empty()){
					basis[j] = aug[i];
					sol2[j] = sol[i];
					ok = 1;
					break;
				}
				else{
					int c = mod - 1ll * aug[i][j] * inv[basis[j][j]] % mod;
					for(int k=0; k<4; k++){
						aug[i][k] += 1ll * c * basis[j][k] % mod;
						aug[i][k] %= mod;
					}
					sol[i] += 1ll * c * sol2[j] % mod;
					sol[i] %= mod;
				}
			}
		}
		if(!ok && sol[i]){
			puts("0 0 0 0");
			return;
		}
	}
	for(int i=3; i>=0; i--){
		if(!basis[i].empty()){
			for(int j=i+1; j<4; j++){
				sol2[i] += mod - 1ll * basis[i][j] * sol2[j] % mod;
				sol2[i] %= mod;
			}
			sol2[i] = 1ll * sol2[i] * inv[basis[i][i]] % mod;
		}
	}
	for(int i=0; i<4; i++){
		printf("%d ", sol2[i]);
	}
	puts("");
}

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

int main(){
	int t;
	cin >> mod >> t;
	for(int i=1; i<mod; i++) inv[i] = ipow(i, mod-2);
	while(t--){
		int a, b, c, d;
		scanf("%d %d %d %d",&a,&b,&c,&d);
		aug = {{a, -b, -c, -d}, {b, a, -d, c}, {c, d, a, -b}, {d, -c, b, a}};
		sol = {1, 0, 0, 0};
		for(int i=0; i<4; i++){
			for(int j=0; j<4; j++){
				aug[i][j] += mod;
				aug[i][j] %= mod;
			}
		}
		solve();
	}
}

Compilation message

Q.cpp: In function 'int main()':
Q.cpp:74:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&a,&b,&c,&d);
                                   ^

Subtask #1
1.0 / 1.0

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

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 2412 KB Output is correct
2 Correct 219 ms 2412 KB Output is correct
3 Correct 243 ms 2412 KB Output is correct
4 Correct 239 ms 2412 KB Output is correct
5 Correct 249 ms 2412 KB Output is correct
6 Correct 246 ms 2412 KB Output is correct
7 Correct 249 ms 2412 KB Output is correct
8 Correct 253 ms 2412 KB Output is correct
9 Correct 259 ms 2412 KB Output is correct
10 Correct 263 ms 2412 KB Output is correct
11 Correct 276 ms 2412 KB Output is correct
12 Correct 279 ms 2412 KB Output is correct
13 Correct 286 ms 2412 KB Output is correct
14 Correct 316 ms 2412 KB Output is correct
15 Correct 303 ms 2412 KB Output is correct