Advertisement
Guest User

Untitled

a guest
Mar 20th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
  5. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6. #pragma comment(linker, "/STACK:16777216")
  7.  
  8. #define all(x) (x).begin(), (x).end()
  9. #define rall(x) (x).rbegin(), (x).rend()
  10. #define mp make_pair
  11. #define exitn return cout<<"NO",0
  12. #define exity return cout<<"YES",0
  13. #define display(a,s, n) \
  14. { \
  15. cout << #a << " = {"; \
  16. for (int qwq = (s); qwq < (n); ++qwq) \
  17. if (qwq == (s)) \
  18. cout << a[qwq]; \
  19. else \
  20. cout << ", " << a[qwq]; \
  21. cout << "}" << endl; \
  22. }
  23.  
  24. using namespace std;
  25. using namespace __gnu_pbds;
  26.  
  27. typedef long long ll;
  28. typedef vector<ll> vll;
  29. typedef unsigned long long ull;
  30. typedef long double ld;
  31. typedef pair<ll,ll> pll;
  32. typedef vector<vll> matrix;
  33. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  34.  
  35. const ll INF = 1e14 + 810;
  36. const ll SIZE = 2e5 + 1;
  37. const ll MOD1 = 1e9 + 7,MOD2 = 119 *(1 << 23) + 1;
  38. const ll BASE1 = 47, BASE2 = 43;
  39. const ll M = 5e3 + 1;
  40. matrix RES;
  41.  
  42. ostream& operator <<(ostream& out,vector<vll> x)
  43. {
  44. out<<"\n--------\n";
  45. for (int i = 0; i < x.size(); i++)
  46. {
  47. for (int j = 0; j < x[i].size(); j++) out<<x[i][j]<<" ";
  48. out<<endl;
  49. }
  50. out<<"--------\n";
  51. return out;
  52. }
  53.  
  54. ostream& operator <<(ostream& out,pll x)
  55. {
  56. out<<x.first<<" "<<x.second<<endl;
  57. return out;
  58. }
  59.  
  60. void what_guys_anime()
  61. {
  62. //freopen("input.txt", "r", stdin);
  63. //freopen("output.txt","w",stdout);
  64. ios_base::sync_with_stdio(0);
  65. cout<<fixed<<setprecision(10);
  66. cin.tie(0);
  67. cout.tie(0);
  68. }
  69. matrix mul(matrix m1,matrix m2)
  70. {
  71. //vector<vll> a(высота,vll(ширина));
  72. ll x1 = m1.size(), y1 = m1[0].size(), x2 = m2.size() ,y2 = m2[0].size();
  73. if (y1 != x2) return m1;
  74. matrix ans(x1,vll(y2));
  75. for (int i = 0; i < x1; i++)
  76. {
  77. for (int j = 0; j < y2; j++)
  78. {
  79. ll s = 0;
  80. for (int k = 0; k < x2; k++)
  81. {
  82. s += m1[i][k] * m2[k][j];
  83. s %= MOD2;
  84. }
  85. ans[i][j] = s;
  86. }
  87. }
  88. return ans;
  89. }
  90. pair<matrix,matrix> LU_decomposition(matrix& a)
  91. {
  92. matrix l(a.size(),vll(a.size())),u(a.size(),vll(a.size()));
  93. ll n = a.size();
  94. for (int i = 0; i < n; i++)
  95. {
  96. for (int k = i; k < n; k++)
  97. {
  98. ll sum = 0;
  99. for (int j = 0; j < i; j++) sum += (l[i][j] * u[j][k]);
  100. u[i][k] = a[i][k] - sum;
  101. }
  102. for (int k = i; k < n; k++)
  103. {
  104. if (i == k)
  105. {
  106. l[i][k] = 1;
  107. continue;
  108. }
  109. ld sum = 0;
  110. for (int j = 0; j < i; j++) sum += (l[k][j] * u[j][i]);
  111. l[k][i] = (a[k][i] - sum) / u[i][i];
  112. }
  113. }
  114. return {l,u};
  115. }
  116. /*
  117. A * x = b;
  118. A = L * U;
  119. L * U * x = b;
  120. L * y = b;
  121. U * x = y;
  122.  
  123. */
  124. vector<ld> solve(pair<matrix,matrix> lu,vll right)
  125. {
  126. //Ly = b;
  127. ld sum = 0;
  128. matrix l = lu.first, u = lu.second;
  129. ll n = l.size();
  130. matrix y(n,vll(1));
  131. for (int i = 0; i < n; i++)
  132. {
  133. sum = 0;
  134. for (int j = 0; j < i; j++) sum += y[j][0] * l[i][j];
  135. y[i][0] = (right[i] - sum)/l[i][i];
  136. }
  137. // Ux = y
  138. vector<ld> ans(n);
  139. vector<ld> error(n,INF);
  140. for (int i = n - 1; i >= 0; i--)
  141. {
  142. sum = 0;
  143. for (int j = n - 1; j > i; j--) sum += (ans[j] * (ld)u[i][j]);
  144. if (u[i][i]) ans[i] = (y[i][0] - sum)/(ld)u[i][i];
  145. //else return error;
  146. }
  147. return ans;
  148. }
  149. int main(){
  150. what_guys_anime();
  151. ll n;
  152. cin>>n;
  153. matrix arr(n,vll(n));
  154. for (int i = 0; i < n; i++)
  155. {
  156. for (int j = 0; j < n; j++) cin>>arr[i][j];
  157. }
  158. vll right(n);
  159. for (int i = 0; i < n; i++) cin>>right[i];
  160. vector<ld> ans = solve(LU_decomposition(arr),right);
  161. display(ans,0,n);
  162. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement