提出 #32926371

---

ソースコード 拡げる

/** @file
 * @ingroup


 */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void O(const T &x) { cout << x << '\n'; }
template <typename T, typename... W> inline void O(const T &x, const W &...b) {
  cout << x << ' ';
  O(b...);
}
template <typename T> inline void rd(T &x) { cin >> x; }
template <typename T, typename... W> inline void rd(T &x, W &...b) {
  cin >> x;
  rd(b...);
}
#ifndef MISAKA
#define err(...)
#else
#define err(...) fprintf(stderr, __VA_ARGS__)
#endif
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef long double dbl;
typedef pair<int, int> pii;
typedef uniform_int_distribution<int> r32;
typedef uniform_int_distribution<i64> r64;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define shuf(L, R) shuffle((L), (R), rng)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define FOR(i, j, k) for (int i = (j); i <= (k); ++i)
#define ROF(i, j, k) for (int i = (k); i >= (j); --i)
template <typename T> inline void ckmin(T &a, const T &b) { a = min(a, b); }
template <typename T> inline void ckmax(T &a, const T &b) { a = max(a, b); }
//#define IOFILE "ex"
//#define MULTI
const int N = 1e5+5;
const int mod = 998244353;

struct mat {
  int a[2][2] = {};
  mat operator+(const mat &r) const {
    mat ret;
    FOR(i,0,1) FOR(j,0,1) {
      ret.a[i][j] = (a[i][j] + r.a[i][j]) % mod;
    }
    return ret;
  }
  mat operator*(const mat &r) const {
    mat ret;
    FOR(i,0,1) FOR(j,0,1) FOR(k,0,1) {
      ret.a[i][j] = (ret.a[i][j] + 1ll * a[i][k] * r.a[k][j]) % mod;
    }
    return ret;
  }
  mat operator*(const int &x) const {
    mat ret;
    FOR(i,0,1) FOR(j,0,1) {
      ret.a[i][j] = 1ll * a[i][j] * x % mod;
    }
    return ret;
  }
  inline int val() {
    return a[1][0];
  }
};

const mat h = {{{1,1},{1,0}}};
const mat ih = {{{0,1},{1,mod-1}}};
const mat e = {{{1,0},{0,1}}};

mat q_pow(i64 a) {
  mat ret = e, hi = h;
  while (a) {
    if (a & 1) ret = ret * hi;
    hi = hi * hi;
    a >>= 1;
  }
  return ret;
}

mat iq_pow(i64 a) {
  mat ret = e, hi = ih;
  while (a) {
    if (a & 1) ret = ret * hi;
    hi = hi * hi;
    a >>= 1;
  }
  return ret;
}

i64 a[N];
mat H[N], iH[N];
int f[N];

inline void sol() {
  int n;
  i64 S;
  rd(n, S);
  FOR(i,1,n) rd(a[i]);
  a[++n] = S;
  FOR(i,1,n) H[i] = q_pow(a[i]), iH[i] = iq_pow(a[i]);
  mat pre;
  FOR(i,1,n) {
    f[i] = (H[i].val() + mod - (H[i] * pre).val()) % mod;
    pre = pre + iH[i] * f[i];
  }
  O(f[n]);
}

int main() {
#ifndef MISAKA
#ifdef IOFILE
  freopen(IOFILE ".in", "r", stdin);
  freopen(IOFILE ".out", "w", stdout);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
#endif
#ifdef MULTI
  int T;
  cin >> T;
  while (T--)
#endif
    sol();
  return 0;
}

提出情報

ジャッジ結果