求助一个很奇怪的问题
查看原帖
求助一个很奇怪的问题
360930
Jairon314楼主2022/1/24 14:14

自己瞎写的高斯消元,能过 1n1001 \le n \le 100 的点,但是数组大小开到 400400400*400 了以后就会全 TLE,不知道是为什么...

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
 
#define int long long
 
/***** Fast_IO *****/
 
using std::cin;
using std::cout;
using vii = std::vector<int> ;
using pii = std::pair<int,int> ;
 
namespace IO{
	char buf[(1<<21)],*p1=buf,*p2=buf,buf1[(1<<21)]; int _=0;
 
	inline char gc (){
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<21),stdin),p1==p2)?EOF:*p1++;
	}
 
	#define gc getchar
	#define pc putchar
	#define ONLINE_JUDGE OJ
 
	template<class I>
	inline I read(I &x){
		x=0; I f=1; char c=gc(); if(c==EOF){ return -1; }
		while(c<'0'||c>'9'){ if(c=='-'){ f=f*(-1); } c=gc(); }
		while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48); c=gc(); }
		return x=x*f;
	}
 
	template<typename I,typename ...Args>
	inline void read(I &a, Args &...args){
		read(a),read(args...);
	}
 
	template<class I>
	inline void write(I x){
		if(x==0){ pc('0'); return; }
		int tmp=x>0?x:(-x),cnt=0;
		if(x<0){ pc('-'); }
		while(tmp){ buf[cnt++]=(tmp%10)+'0'; tmp/=10; }
		while(cnt){ pc(buf[--cnt]); }
		return;
	}
	
	template<class I>
	inline void chmax(I &x,I y){ return x=max(x,y),void(); }
	
	template<class I>
	inline void chmin(I &x,I y){ return x=min(x,y),void(); }
 
	#define out(x) write(x),pc(' ')
	#define outn(x) write(x),pc('\n')
	#define assi() pc('\t')
	#define FOR(i,a,b) for(int i(a);i<=(b);++i)
	#define ROF(i,a,b) for(int i(a);i>=(b);--i)
	#define FORs(i,a,b,s) for(int i(a);i<=(b);i+=(s))
	#define ROFs(i,a,b,s) for(int i(a);i>=(b);i-=(s))
	#define next(i,now) for(int i(link[now]);i;i=edge[i].nexty)
	#define each(i,v) for(auto &i:v)
	#define all(v) v.begin(),v.end()
	#define sqr(k) ((k)*(k))
	#define inf 0x3f3f3f3f
	#define pb push_back
	#define mp make_pair
	#define fir first
	#define sec second
}using namespace IO;
 
/***** Fast_IO *****/
 
#define maxn 1000010
#define SIZE 101

const int mod = 1e9+7;

int qpow(int a,int b){
	int res=1,tmp=a;
	while(b){ if(b&1){ res=(res*tmp)%mod; } tmp=(tmp*tmp)%mod; b>>=1; }
	return res;
}

int inv(int k){ return qpow(k,mod-2); }

template<class I>
struct Matrix{
	int h,l;
	I val[SIZE][SIZE];
	I ext[SIZE];
	Matrix<I>(){}
	Matrix<I>(int h_,int l_,bool is_E=0):h(h_),l(l_){ memset(val,0,sizeof val); if(is_E){ FOR(i,1,h){ val[i][i]=1; } } }
	Matrix<I>(Matrix<I> &mat):h(mat.h),l(mat.l){ FOR(i,1,h){ FOR(j,1,l){ val[i][j]=mat.val[i][j]; } } FOR(i,1,h){ ext[i]=mat.ext[i]; } }
	void input(int h_,int l_,bool is_ext=0){ h=h_,l=l_; FOR(i,1,h){ FOR(j,1,l){ cin>>(val[i][j]); } if(is_ext){ cin>>(ext[i]); } } }
	void print(bool is_ext=0){ FOR(i,1,h){ FOR(j,1,l){ cout<<(val[i][j])<<" "; } if(is_ext){ printf("ext: "); cout<<(ext[i])<<endl; } pc('\n'); } }

	// 基本运算

	Matrix<I> operator *(const I &p) const { Matrix<I> res(h,l); FOR(i,1,h){ FOR(j,1,l){ res.val[i][j]=val[i][j]*p; } } return res; }					// 矩阵数乘
	Matrix<I> operator +(const Matrix<I> &p) const { Matrix<I> res(h,l); FOR(i,1,h){ FOR(j,1,l){ res.val[i][j]=val[i][j]+p.val[i][j]; } } return res; }	// 矩阵加法

	Matrix<I> operator *(const Matrix<I> &p) const {
		Matrix<I> res(h,p.l);
		FOR(i,1,h){ FOR(j,1,p.l){ FOR(k,1,l){ res.val[i][j]=(res.val[i][j]+val[i][k]*p.val[k][j]); } } }
		return res;
	} // 矩阵乘法

	Matrix<I> operator ^(int b){
		Matrix<I> res(h,l,1),tmp(*this);
		while(b){ if(b&1){ res=(res*tmp); } tmp=(tmp*tmp); b>>=1; }
		return res;
	} // 矩阵快速幂

	// 初等变换 ----> 经有限次初等变换后的矩阵(B)与原矩阵(A)等价 ( A,B 均为 m×n 矩阵 )
	// A ~ B <=> 存在 m 阶可逆矩阵(P)及 n 阶可逆矩阵(Q), 使得 PAQ = B

	Matrix<I> r_swap(int i,int j){ Matrix<I> res(*this); swap(res.val[i],res.val[j]); return res; }							// 交换两行
	Matrix<I> T(){ Matrix<I> res(l,h); FOR(i,1,h){ FOR(j,1,l){ res.val[j][i]=val[i][j]; } } return res; }					// 矩阵转置
	Matrix<I> K(int i,I k){ Matrix<I> res(*this); FOR(j,1,l){ res.val[i][j]=(res.val[i][j]*k%mod+mod)%mod; } return res; }					// 用 K 乘以某一行
	Matrix<I> S(int i,int ii,I k){ Matrix<I> res(*this); FOR(j,1,l){ res.val[ii][j]=(val[i][j]*k%mod+val[ii][j]+mod)%mod; } return res; }	// 用 K 乘以某一行加到另一行
};

Matrix<int> A,B;

int n;

void Gauss(){
	FOR(i,1,n){
		int tmp=i;
		FOR(j,i+1,n){ tmp=fabs(A.val[j][i])>fabs(A.val[tmp][i])?j:tmp; }
		if(tmp!=i){ A=A.r_swap(i,tmp); B=B.r_swap(i,tmp); }
		if(A.val[i][i]){
			int value=A.val[i][i];
			A=A.K(i,inv(value)); B=B.K(i,inv(value));
			FOR(j,1,n){ if(i!=j){ value=A.val[j][i]; A=A.S(i,j,(mod-value)%mod); B=B.S(i,j,(mod-value)%mod); } }
		} else{ puts("No Solution"); exit(0); }
	}
}

signed main(){
	read(n);
	A.input(n,n);
	B=Matrix<int>(n,n,1);
	Gauss();
	B.print();
	return 0;
}

把 Matrix 里面的 val 数组开成 400400400*400 就会全寄...本地也会炸...求助如何处理

2022/1/24 14:14
加载中...