// Sparse fixed-order modular LU. A floating ordering is only a heuristic: every // modular pivot and the residual are checked, and a zero pivot rejects this prime. #include #include #include #include #include #include #include #include #include #include using namespace std; using ll=long long; using Entry=pair; ll P; ll norm(ll a){a%=P;return a<0?a+P:a;} ll mul(ll a,ll b){return (a*b)%P;} // P<2^30 makes signed64 multiplication safe. ll power(ll a,ll e){ll v=1;while(e){if(e&1)v=mul(v,a);a=mul(a,a);e>>=1;}return v;} struct Factors{int n;vector> lo,up;vector inv;}; void save(const Factors&f,string path){ofstream o(path);o<>f.n>>P;if(!s)throw string("bad factor file");f.lo.resize(f.n);f.up.resize(f.n);f.inv.resize(f.n); for(int k=0;k>a>>b>>f.inv[k];f.lo[k].resize(a);f.up[k].resize(b);for(auto &x:f.lo[k])s>>x.first>>x.second;for(auto &x:f.up[k])s>>x.first>>x.second;}if(!s)throw string("truncated factor file");return f;} vector solve(const Factors&f,vectorb){for(int k=0;kx(f.n);for(int k=f.n-1;k>=0;k--){ll v=b[k];for(auto [j,a]:f.up[k])if(j>k)v=norm(v-mul(a,x[j]));x[k]=mul(v,f.inv[k]);}return x;} size_t rss(){rusage q;getrusage(RUSAGE_SELF,&q); #ifdef __APPLE__ return q.ru_maxrss; #else return q.ru_maxrss*1024ULL; #endif } int main(int argc,char**argv){try{ if(argc>=3&&string(argv[1])=="solve"){auto f=load(argv[2]);vectorb(f.n);while(cin>>b[0]){for(int i=1;i>b[i]))throw string("truncated RHS");for(auto &v:b)v=norm(v);auto x=solve(f,b);for(int i=0;i=(1LL<<30))throw string("prime range"); ifstream in(argv[2]);int n,nz;in>>n>>nz;if(!in||n<=0||nz<0)throw string("bad input"); vector> a(n);vector> inc(n);vector> orig(n); for(int t=0;t>i>>j>>v;if(i<0||i>=n||j<0||j>=n||!in)throw string("bad index");v=norm(v);if(a[i].count(j))throw string("duplicate");a[i][j]=v;inc[j].insert(i);orig[i].push_back({j,v});} vectorb(n);for(auto &v:b)in>>v;if(!in)throw string("bad RHS"); Factors f;f.n=n;f.lo.resize(n);f.up.resize(n);f.inv.resize(n);size_t live=nz,total=0,peak=nz;double t0=double(clock())/CLOCKS_PER_SEC; for(int k=0;ksecond==0){cout<<"FACTOR ZERO_PIVOT "<second,P-2);if(mul(it->second,f.inv[k])!=1)throw string("not invertible"); for(auto e:a[k]){if(e.first dest;for(int i:inc[k])if(i>k)dest.push_back(i);sort(dest.begin(),dest.end()); for(int i:dest){ll v=mul(a[i].at(k),f.inv[k]);f.lo[k].push_back({i,v});a[i].erase(k);inc[k].erase(i);live--; for(auto [j,u]:f.up[k])if(j>k){auto old=a[i].find(j);ll next=norm((old==a[i].end()?0:old->second)-mul(v,u)); if(next==0){if(old!=a[i].end()){a[i].erase(old);inc[j].erase(i);live--;}} else if(old==a[i].end()){a[i][j]=next;inc[j].insert(i);live++;}else old->second=next;}} for(auto [j,u]:f.up[k])inc[j].erase(k);live-=a[k].size();a[k].clear();total+=f.lo[k].size()+f.up[k].size();peak=max(peak,live+total); if(peak>5000000ULL||rss()>1500000000ULL){cout<<"FACTOR FILL_CAP "<170){cout<<"FACTOR CPU_CAP "<