답안 #9588

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9588 2014-09-28T07:30:03 Z pichulia Quaternion inverse (kriii2_Q) C++
4 / 4
492 ms 1248 KB
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef vector<vector<long long int> > mat;
typedef vector<long long int> vi;
long long MOD = 1000000007; 
// a^(-1) mod m (NOTE. m must be prime) 
long long int gcd_ext(long long int a,long long int m) 
{ 
    long long int x,y,q,s[2],t[2],i; 
    int l1,l2;
    l1=0;l2=1;
    s[0]=1;t[0]=0; 
    s[1]=0;t[1]=1; 
    x=m;y=a; 
    for(i=2;y;i++) 
    { 
        q=x/y; 
        s[l1]=s[l1]-q*s[l2]; 
        t[l1]=t[l1]-q*t[l2]; 
        l1^=l2^=l1^=l2;
        y^=x^=y^=x%=y; 
    } 
    return (t[l1]+m+m)%m; 
}
mat mat_add(mat &v1,mat &v2){
    mat ret(v1.size(),vi(v1[0].size())); 
    for(int i=0;i<v1.size();i++) 
        for(int j=0;j<v1[0].size();j++) 
            ret[i][j]=(ret[i][j]+v1[i][j]+v2[i][j])%MOD; 
    return ret; 
} 
   
mat mat_mul(mat &v1,mat &v2){
    mat ret(v1.size(),vi(v2[0].size())); 
    for(int i=0;i<v1.size();i++) 
        for(int k=0;k<v2.size();k++) 
            for(int j=0;j<v2[0].size();j++) 
                ret[i][j]=(ret[i][j]+v1[i][k]*v2[k][j])%MOD; 
    return ret; 
} 
   
mat mat_pow(mat v1,long long n){
    mat ret(v1.size(),vi(v1.size())); 
    for(int i=0;i<v1.size();i++) ret[i][i]=1; 
    while(n!=0){ 
        if(n&1) ret=mat_mul(ret,v1); 
        v1=mat_mul(v1,v1); 
        n=n>>1; 
    } 
    return ret; 
}
// matrix (nxm) * ans (m*1) = b(n*1)
void gauss(mat &A, vi &b)
{
    int i, j, l;
    int si;
    for(i=si=0; si<A.size() && i<A[0].size(); i++)
    {
        for(j=si; j<A.size(); j++)
        {
            if(A[j][i])
            {
                vi tmp = A[si];
                A[si] = A[j];
                A[j] = tmp;
               long long int tmp2 = b[si];
                b[si] = b[j];
                b[j] = tmp2;
                break;
            }
        }
        if(j==A.size()) continue;
        long long int k = gcd_ext(A[si][i],MOD);
        for(j=i; j<A[0].size(); j++)
            A[si][j]=(A[si][j]*k)%MOD;
        b[si]=(b[si]*k)%MOD;
  
        for(j=si+1; j<A.size(); j++)
        {
            k = A[j][i];
            for(l=i; l<A[0].size(); l++)
            {
                A[j][l] = (A[j][l] - k * A[si][l] + (long long)MOD*MOD)%MOD;
            }
            b[j] = (b[j] -  b[si]*k + (long long)MOD*MOD)%MOD;
        }
        si++;
    }
}
// return Ax = b solution. if x have -1, mean "no solution"
vi get_ans(mat A, vi b)
{
	
    int i, j, l;
    gauss(A,b);
    int si;
    int pre_i = A[0].size();
    vi ans = vi(A[0].size(), 0);
    si = A.size() - 1; 
    i=pre_i;
    for(;si>=0 && i>=0; si--)
    {
        for(j=0;j<A[0].size();j++)
            if(A[si][j])
                break;
        i = j;
        if(i == A[0].size())
        {
            if(b[si])
            {
                // no solution => ans have negative value
				return vi(A[0].size(),0);
            }
            continue;
        }
        // set special solutions
        for(j=i+1; j<pre_i; j++)
        {
            ans[j] = 0;
        }
        long long int k = gcd_ext(A[si][i],MOD);
        ans[i] = (b[si]*k)%MOD;
        for(j=i;j<pre_i; j++)
        {
            for(l=0;l<=si;l++)
            {
                k = A[l][j];
                b[l] = (b[l] - ans[j] * k + MOD*MOD)%MOD;
            }
        }
        pre_i = i;
    }
    return ans;
}
int main()
{
	int t;
	scanf("%lld %d",&MOD, &t);
	while(t--)
	{
		long long int a,b,c,d;
		mat A;
		scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
		vi tmp;
		A.clear();
		tmp.clear();
		tmp.push_back(a);
		tmp.push_back((MOD-b)%MOD);
		tmp.push_back((MOD-c)%MOD);
		tmp.push_back((MOD-d)%MOD);
		A.push_back(tmp);
		tmp.clear();
		tmp.push_back(b);
		tmp.push_back(a);
		tmp.push_back((MOD-d)%MOD);
		tmp.push_back(c);
		A.push_back(tmp);
		tmp.clear();
		tmp.push_back(c);
		tmp.push_back(d);
		tmp.push_back(a);
		tmp.push_back((MOD-b)%MOD);
		A.push_back(tmp);
		tmp.clear();
		tmp.push_back(d);
		tmp.push_back((MOD-c)%MOD);
		tmp.push_back(b);
		tmp.push_back(a);
		A.push_back(tmp);
		vi bb;
		bb.clear();
		bb.push_back(1);
		bb.push_back(0);
		bb.push_back(0);
		bb.push_back(0);
		vi ans = get_ans(A, bb);
		printf("%lld %lld %lld %lld\n",ans[0],ans[1],ans[2],ans[3]);
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1248 KB Output is correct
2 Correct 0 ms 1248 KB Output is correct
3 Correct 0 ms 1248 KB Output is correct
4 Correct 8 ms 1248 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 316 ms 1248 KB Output is correct
2 Correct 388 ms 1248 KB Output is correct
3 Correct 392 ms 1248 KB Output is correct
4 Correct 416 ms 1248 KB Output is correct
5 Correct 412 ms 1248 KB Output is correct
6 Correct 432 ms 1248 KB Output is correct
7 Correct 436 ms 1248 KB Output is correct
8 Correct 468 ms 1248 KB Output is correct
9 Correct 460 ms 1248 KB Output is correct
10 Correct 464 ms 1248 KB Output is correct
11 Correct 484 ms 1248 KB Output is correct
12 Correct 468 ms 1248 KB Output is correct
13 Correct 484 ms 1248 KB Output is correct
14 Correct 472 ms 1248 KB Output is correct
15 Correct 492 ms 1248 KB Output is correct