萌新求助 WA#8和#10(在线求大佬hack掉,挺急的(谢谢大佬))

P2455 [SDOI2006] 线性方程组

SpeMars @ 2021-10-19 20:44:12

我的做法是判断同构方程来判断无解和无数解

但是#8和#10一直过不了

翻了很多帖子,全部的hack都没有hack掉

在线求大佬解答。

%%%谢谢大佬storz

code:

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define ld long double
using namespace std;
const ld eps=1e-7;
const int N=111,p=998244353;
int n;
bool vis[N];
ld a[N][N],b[N];
int A[N][N],B[N];
int fpow(int x,int y){
    int s=1;
    for(;y;(y>>=1)){
        if(y&1)s=(s*x)%p;
        x=(x*x)%p;
    }
    return s;
} 
void Gause_mod(int n){
    for(int i=1;i<=n;++i){
        //因为这是在%p的意义下,所以不会出现精度问题
        //又因为第i个方程的第i项绝对不是0,所以不需要交换
        int inv=fpow(A[i][i],p-2);
        for(int j=1;j<=n;++j){
            if(i==j)continue;
            int tt=A[j][i]*inv%p;
            for(int k=i;k<=n+1;++k)A[j][k]=(A[j][k]-A[i][k]*tt%p+p)%p;
        }
    }
    for(int i=1;i<=n;++i)B[i]=A[i][n+1]*fpow(A[i][i],p-2)%p;
    return;
}
void Gause(int n){
    for(int i=1;i<=n;++i){
        int r=i;
        for(int j=i+1;j<=n;++j)if(fabs(a[r][i])<fabs(a[j][i]))r=j;
//      if(fabs(a[r][i])<eps)return;
        if(i!=r)swap(a[i],a[r]);
        ld div=a[i][i];
        for(int j=i;j<=n+1;++j)a[i][j]/=div;
        for(int j=i+1;j<=n;++j){
            div=a[j][i];
            for(int k=i;k<=n+1;++k)a[j][k]=(a[j][k]-a[i][k]*div);
        }
    }
    b[n]=a[n][n+1];
    for(int i=n-1;i>=1;--i){
        for(int j=i+1;j<=n;++j){
            a[i][n+1]-=a[i][j]*a[j][n+1];
        }
        b[i]=a[i][n+1];
    }
    return;
}
int pd(int i,int j){
    bool ok=true;
    for(int k=1;k<=n;++k){
        if(A[i][k]!=A[j][k]){
            ok=false;
            break;
        }
    }
    if(ok==false)return 0;
    if(B[i]==0||B[j]==0)for(;;);
    if((A[i][n+1]==A[j][n+1])&&(B[i]==B[j]))return 1;
    return 2;
}
signed main(){
//  printf("%lld\n",__gcd(0,0));
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n+1;++j){
            scanf("%lld",A[i]+j);
            a[i][j]=(long double)(A[i][j]);
        }
    }
    bool many=false;
    for(int i=1;i<=n;++i){
        int g=A[i][1];
        for(int j=2;j<=n;++j)g=__gcd(A[i][j],g);
        if(g!=0)for(int j=1;j<=n;++j)A[i][j]/=g;
        if(g==0&&A[i][n+1]!=0){
            puts("-1");
            return 0;
        }
        if(g==0&&A[i][n+1]==0){
            many=true;
            vis[i]=true;
        }
        else{
            B[i]=g;
            int di=__gcd(B[i],A[i][n+1]);
            B[i]/=di,A[i][n+1]/=di;
        }
    }
    for(int i=1;i<n;++i){
        if(vis[i])continue;
        for(int j=i+1;j<=n;++j){
            if(vis[j])continue;
            int sao=pd(i,j);
            if(sao==1)many=true;
            if(sao==2){
                puts("-1");
                return 0;
            }
        }
    }
    if(many){
        puts("0");
        return 0;
    }
    Gause(n);
    for(int i=1;i<=n;++i){
        if(fabs(b[i])<eps)printf("x%lld=0.00\n",i);
        else printf("x%lld=%.2Lf\n",i,b[i]);
    }
    return 0;
}
/*
3
1 2 1 1
3 6 3 3
2 4 2 3

3
-2 -1 1 1
0 1 -1 5
0 1 1 0
*/

最后再次表达深深的谢意!


by _Diu_ @ 2021-10-19 21:40:33

in:
3
1 1 0 0
0 1 1 0
1 2 1 1
out:
-1

您输出的是:

x1=nan
x2=-inf
x3=inf

by SpeMars @ 2021-10-20 15:51:35

@我不是奆佬 storz%%%


|