#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 time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
