矩阵求逆不开O2 TLE 开O2AC,是否有什么问题
查看原帖
矩阵求逆不开O2 TLE 开O2AC,是否有什么问题
289304
HAuCl4楼主2023/1/13 22:04

RT,怕实战时写炸调不出来。不知道程序是否有问题。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int N=405;
int n,m;
ll a[N][2*N]; 
void ext(){
	printf("No Solution");
	exit(0);
}
void dbg(){
    for(int i=1;i<=n;i++)
    {
        for(int j=n+1;j<=m-1;j++) printf("%lld ",a[i][j]);
        printf("%lld\n",a[i][m]);
    }
}
ll ksm(ll a,ll b){
	ll tmp=a,ret=1;
	while(b){if(b&1) (ret*=tmp)%=mod; (tmp*=tmp)%=mod; b>>=1;}
	return ret;
}
#define inv(x) ksm(x,mod-2)
void swp(int h1,int h2){for(int i=1;i<=m;i++)swap(a[h1][i],a[h2][i]);}
void add(int h1,int h2){for(int i=1;i<=m;i++)(a[h2][i]+=a[h1][i])%=mod;}
void del(int h1,int h2){for(int i=1;i<=m;i++)(a[h2][i]-=a[h1][i])%=mod;}
void mult(int h1,ll b){for(int i=1;i<=m;i++)(a[h1][i]*=b)%=mod;}
void div(int h1,ll b){ll b1=inv(b);for(int i=1;i<=m;i++)(a[h1][i]*=b1)%=mod;}
void clr(int h1){memset(a[h1],0,sizeof(a[h1]));}
void inverse()
{
	for(int j=1;j<=n;j++)
	{
		int i1=-1;
		for(int i=j;i<=n;i++)
			if(a[i][j]!=0)
			{
				i1=i;
				break;
			}
		if(i1==-1) ext();
		swp(i1,j);
		for(int i=j;i<=n;i++)
		{
			if(a[i][j]==0) continue;
			if(i==j) div(i,a[i][i]);
			else
			{
				clr(n+1);
				add(j,n+1);
				mult(n+1,a[i][j]);
				del(n+1,i);
			}
		}
//		dbg();
	}
	for(int i=n;i>=1;i--)
	{
		for(int j=1;j<=i-1;j++)
		{
			clr(n+1);
			add(i,n+1);
			mult(n+1,a[j][i]);
			del(n+1,j);
		}
		for(int j=n+1;j<=m;j++) (a[i][j]+=mod)%=mod;
	}
}
int main()
{
	memset(a,0,sizeof(a));
	scanf("%d",&n);
	m=2*n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			scanf("%lld",&a[i][j]);
		a[i][n+i]=1;
	}
	inverse();
	dbg();
//	for(int i=1;i<=n;i++) printf("%.2lf\n",a[i][n+1]);
	return 0;
}
2023/1/13 22:04
加载中...