제출 #9588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
9588		pichulia	Quaternion inverse (kriii2_Q)	C++98	4 / 4	492 ms	1248 KiB

Q

#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]);
	}
}

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3