Function Thomas

Math/Thomas Algorithm.cpp:49–65

n equations of form: a_i*x_{i-1}+b_i*x_i+c_i*x_{i+1}=d_i, for i=1 to n where a_1=0,c_n=0 matrix form: b1 c1 0 0 0 | x1 d1 a2 b2 c2 0 0 | x2 d2 0 a3 b3 c3 0 | x3 = d3 0 0 a4 b4 c4| x4 d4 0 0 0 a5 b5| x5 d5 **/ Thomas algorithm for solving tri-digonal system of equations in O(n) This algorithm is not stable in general. If |a[i][i]| >= |a[i][j]|(i != j) for all i a

// then denominator will have 0 at some instant
// There are others unstable cases too
vector<mint> Thomas(vector<vector<mint>> a) {
  int n = a.size();
  for (int i = 1; i < n; i++) {
    mint x = a[i][0] * a[i - 1][1].inv();
    a[i][1] -= x * a[i - 1][2];
    a[i][3] -= x * a[i - 1][3];
  }
  for (int i = n - 2; i >= 0; i--) {
    mint x = a[i][2] * a[i + 1][1].inv();
    a[i][3] -= x * a[i + 1][3];
  }
  vector<mint> ans;
  for(int i = 0; i < n; i++) {
    ans.push_back(a[i][3] * a[i][1].inv());
  }
  return ans;
}
int a[N];
int32_t main() {
  ios_base::sync_with_stdio(0);