제출 #9588

#제출 시각아이디문제언어결과실행 시간메모리
9588pichuliaQuaternion inverse (kriii2_Q)C++98
4 / 4
492 ms1248 KiB
#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]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...