萌新刚学矩阵求逆,不开O2 1.02sTLE求助
查看原帖
萌新刚学矩阵求逆,不开O2 1.02sTLE求助
171487
cmll02楼主2021/2/1 09:40

RT,不知道咋搞了……O2 最大点不到0.3s,不开1.02sT掉一堆……

求差错QAQ

代码:

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
inline int read()
{
	int num=0,f=1;char c=getchar();
	while(c<48||c>57)f=(c=='-'?-1:f),c=getchar();
	while(c>47&&c<58)num=(num<<3)+(num<<1)+(c^48),c=getchar();
	return num*f;
}
#define int long long
const int mod = 1000000007;
int qp(int x,int p)
{
	int res=1;
	while(p)
	{
		if(p&1)res=res*x%mod;
		x=x*x%mod;
		p>>=1;
	}
	return res;
}
struct Mod{
	long long x;
	Mod(int x=0):x(x){}
	Mod operator=(const int& xx)
	{
		x=xx;
		return *this;
	}
	Mod operator+(const Mod &b)
	{
		return (Mod)((x+b.x)%1000000007);
	}
	Mod operator-(const Mod &b)
	{
		return (Mod)((x-b.x+1000000007)%1000000007);
	}
	Mod operator*(const Mod &b)
	{
		return (Mod)((x*b.x)%1000000007);
	}
	Mod operator/(const Mod &b)
	{
	    if(x%b.x==0)return (Mod)(x/b.x);
		return (Mod)(x*qp(b.x,1000000005)%1000000007);
	}
	Mod operator+(const int &b)
	{
		return (Mod)((x+b)%1000000007);
	}
	Mod operator-(const int &b)
	{
		return (Mod)((x-b+1000000007)%1000000007);
	}
	Mod operator*(const int &b)
	{
		return (Mod)((x*b)%1000000007);
	}
	Mod operator/(const int &b)
	{
	    if(x%b==0)return (Mod)(x/b);
		return (Mod)(x*qp(b,100000005)%1000000007);
	}
};
Mod a[405][805];
template <typename T>
inline void swap(T &a,T &b)
{
	T t=a;a=b,b=t;
}
signed main()
{
	int n=read();
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)a[i][j]=read();
	for(int i=0;i<n;i++)a[i][i+n]=1;
	for(int i=0;i<n;i++)
	{
		int amxn=i;
		for(int j=i+1;j<n;j++)if(a[j][i].x>a[i][i].x)amxn=j;
		for(int j=0;j<n+n;j++)swap(a[i][j],a[amxn][j]);
		if(a[i][i].x==0)return puts("No Solution")&0;
	//	for(int i=0;i<n;i++,puts(""))
	//		for(int j=0;j<=n;j++)printf("%.2lf ",a[i][j]);puts("");
		Mod x=1;
		x=x/a[i][i];
		for(int j=i+1;j<n+n;j++)a[i][j]=a[i][j]*x;
		a[i][i]=1;
		for(int j=0;j<n;j++)
		{
			if(i^j)
			{
				for(int k=i+1;k<n+n;k++)a[j][k]=a[j][k]-a[j][i]*a[i][k];
				a[j][i]=0;
			}
		}
			
		
	//	for(int i=0;i<n;i++,puts(""))
	//		for(int j=0;j<=n;j++)printf("%.2lf ",a[i][j]);puts("");
	}
	for(int i=0;i<n;i++,puts(""))
		for(int j=n;j<n+n;j++)printf("%d ",a[i][j].x);
	return 0;
}
2021/2/1 09:40
加载中...