萌新求助 WA#8和#10(在线求大佬hack掉,挺急的(谢谢大佬))
查看原帖
萌新求助 WA#8和#10(在线求大佬hack掉,挺急的(谢谢大佬))
374929
SpeMars楼主2021/10/19 20:44

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

但是#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
*/

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

2021/10/19 20:44
加载中...