自己瞎写的高斯消元,能过 1≤n≤100 的点,但是数组大小开到 400∗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 数组开成 400∗400 就会全寄...本地也会炸...求助如何处理