Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #pragma comment(linker, "/STACK:16777216")
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- #define mp make_pair
- #define exitn return cout<<"NO",0
- #define exity return cout<<"YES",0
- #define display(a,s, n) \
- { \
- cout << #a << " = {"; \
- for (int qwq = (s); qwq < (n); ++qwq) \
- if (qwq == (s)) \
- cout << a[qwq]; \
- else \
- cout << ", " << a[qwq]; \
- cout << "}" << endl; \
- }
- using namespace std;
- using namespace __gnu_pbds;
- typedef long long ll;
- typedef vector<ll> vll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef pair<ll,ll> pll;
- typedef vector<vll> matrix;
- typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
- const ll INF = 1e14 + 810;
- const ll SIZE = 2e5 + 1;
- const ll MOD1 = 1e9 + 7,MOD2 = 119 *(1 << 23) + 1;
- const ll BASE1 = 47, BASE2 = 43;
- const ll M = 5e3 + 1;
- matrix RES;
- ostream& operator <<(ostream& out,vector<vll> x)
- {
- out<<"\n--------\n";
- for (int i = 0; i < x.size(); i++)
- {
- for (int j = 0; j < x[i].size(); j++) out<<x[i][j]<<" ";
- out<<endl;
- }
- out<<"--------\n";
- return out;
- }
- ostream& operator <<(ostream& out,pll x)
- {
- out<<x.first<<" "<<x.second<<endl;
- return out;
- }
- void what_guys_anime()
- {
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt","w",stdout);
- ios_base::sync_with_stdio(0);
- cout<<fixed<<setprecision(10);
- cin.tie(0);
- cout.tie(0);
- }
- matrix mul(matrix m1,matrix m2)
- {
- //vector<vll> a(высота,vll(ширина));
- ll x1 = m1.size(), y1 = m1[0].size(), x2 = m2.size() ,y2 = m2[0].size();
- if (y1 != x2) return m1;
- matrix ans(x1,vll(y2));
- for (int i = 0; i < x1; i++)
- {
- for (int j = 0; j < y2; j++)
- {
- ll s = 0;
- for (int k = 0; k < x2; k++)
- {
- s += m1[i][k] * m2[k][j];
- s %= MOD2;
- }
- ans[i][j] = s;
- }
- }
- return ans;
- }
- pair<matrix,matrix> LU_decomposition(matrix& a)
- {
- matrix l(a.size(),vll(a.size())),u(a.size(),vll(a.size()));
- ll n = a.size();
- for (int i = 0; i < n; i++)
- {
- for (int k = i; k < n; k++)
- {
- ll sum = 0;
- for (int j = 0; j < i; j++) sum += (l[i][j] * u[j][k]);
- u[i][k] = a[i][k] - sum;
- }
- for (int k = i; k < n; k++)
- {
- if (i == k)
- {
- l[i][k] = 1;
- continue;
- }
- ld sum = 0;
- for (int j = 0; j < i; j++) sum += (l[k][j] * u[j][i]);
- l[k][i] = (a[k][i] - sum) / u[i][i];
- }
- }
- return {l,u};
- }
- /*
- A * x = b;
- A = L * U;
- L * U * x = b;
- L * y = b;
- U * x = y;
- */
- vector<ld> solve(pair<matrix,matrix> lu,vll right)
- {
- //Ly = b;
- ld sum = 0;
- matrix l = lu.first, u = lu.second;
- ll n = l.size();
- matrix y(n,vll(1));
- for (int i = 0; i < n; i++)
- {
- sum = 0;
- for (int j = 0; j < i; j++) sum += y[j][0] * l[i][j];
- y[i][0] = (right[i] - sum)/l[i][i];
- }
- // Ux = y
- vector<ld> ans(n);
- vector<ld> error(n,INF);
- for (int i = n - 1; i >= 0; i--)
- {
- sum = 0;
- for (int j = n - 1; j > i; j--) sum += (ans[j] * (ld)u[i][j]);
- if (u[i][i]) ans[i] = (y[i][0] - sum)/(ld)u[i][i];
- //else return error;
- }
- return ans;
- }
- int main(){
- what_guys_anime();
- ll n;
- cin>>n;
- matrix arr(n,vll(n));
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < n; j++) cin>>arr[i][j];
- }
- vll right(n);
- for (int i = 0; i < n; i++) cin>>right[i];
- vector<ld> ans = solve(LU_decomposition(arr),right);
- display(ans,0,n);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement