Linear Recurrence

int linear_recurrence(vector<int> a, vector<int> x, int k) {
  int n = a.size();
  vector<int> t(2*n+1);

  function<vector<int> (int)> rec = [&](int k) {
    vector<int> c(n);
    if (k < n) c[k] = 1;
    else {
      vector<int> b = rec(k / 2);
      fill(begin(t), end(t), 0);
      for (int i = 0; i < n; ++i) 
        for (int j = 0; j < n; ++j)
          t[i+j+(k&1)] += b[i]*b[j];
      for (int i = 2*n-1; i >= n; --i) 
        for (int j = 0; j < n; j++) 
          t[i-n+j] += a[j]*t[i];
      for (int i = 0; i < n; ++i) 
        c[i] = t[i];
    }
    return c;
  };
  vector<int> c = rec(k);
  int ans = 0;
  for (int i = 0; i < x.size(); ++i) 
    ans += c[i]*x[i];
  return ans;
}