不错的矩阵快速幂优化 dp 练习题。
考虑一个朴素 dp，\(f_i\) 为组成和为 \(i\) 且用到的数都是奇数的方案数。有转移：
\[f_i = \begin{cases} \sum\limits_{j=0}^{i-1} [i \bmod 2 \ne j \bmod 2] f_j & i \notin A \\ 0 & i \in A \end{cases} \]考虑前缀和优化，设 \(g_{i, j} = \sum\limits_{i=0}^i [i \bmod 2 = j] f_i\)，那么：
\[f_i = \begin{cases} g_{i, 1 - i \bmod 2} & i \notin A \\ 0 & i \in A \end{cases} \]\[g_{i, i \bmod 2} = g_{i - 1, i \bmod 2} + f_i = g_{i - 1, i \bmod 2} + [i \notin A] g_{i - 1, 1 - i \bmod 2} \]\[g_{i, 1 - i \bmod 2} = g_{i - 1, 1 - i \bmod 2} \]至此得到了一个 \(O(S)\) 的做法。
发现 \([0, S]\) 被 \(A_i\) 分成若干段，并且每一段的转移方程重复。为了方便把 \(i \bmod 2 = 1, i \bmod 2 = 0\) 的相邻两个 \(i\) 放一起考虑，那么相当于 \(g'_0 = 2g_0 + g_1, g'_1 = g_0 + g_1\)。容易刻画成矩阵形式，然后分段转移。注意处理一些端点奇偶性不相同的情况。
时间复杂度 \(O(n \log S)\)。
code
// Problem: Ex - Odd Steps
// Contest: AtCoder - AtCoder Beginner Contest 258
// URL: https://atcoder.jp/contests/abc258/tasks/abc258_h
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
const ll mod = 998244353;
ll n, m, a[maxn], f[maxn], g[2];
struct matrix {
ll a[2][2];
matrix() {
mems(a, 0);
}
} ma, I, ans;
inline matrix operator * (matrix a, matrix b) {
matrix res;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j] % mod) % mod;
}
}
}
return res;
}
inline matrix qpow(matrix a, ll p) {
matrix res = I;
while (p) {
if (p & 1) {
res = res * a;
}
a = a * a;
p >>= 1;
}
return res;
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
a[n + 1] = m + 1;
ma.a[0][0] = 2;
ma.a[0][1] = ma.a[1][0] = ma.a[1][1] = 1;
I.a[0][0] = I.a[1][1] = 1;
ans.a[0][0] = 1;
for (int i = 1; i <= n + 1; ++i) {
if (a[i] - a[i - 1] <= 5) {
for (ll x = a[i - 1] + 1; x < a[i]; ++x) {
ans.a[0][x & 1] = (ans.a[0][x & 1] + ans.a[0][(x & 1) ^ 1]) % mod;
}
} else {
ll x = a[i - 1] + 1;
if (x % 2 == 0) {
ans.a[0][x & 1] = (ans.a[0][x & 1] + ans.a[0][(x & 1) ^ 1]) % mod;
++x;
}
matrix t = qpow(ma, (a[i] - x) / 2);
x += (a[i] - x) / 2 * 2;
ans = ans * t;
if (x != a[i]) {
ans.a[0][x & 1] = (ans.a[0][x & 1] + ans.a[0][(x & 1) ^ 1]) % mod;
}
}
}
printf("%lld\n", ans.a[0][(m & 1) ^ 1]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
/*
g[i][1] = g[i - 1][0] + g[i - 1][1]
g[i][0] = g[i - 1][0] + g[i][1] = 2 * g[i - 1][0] + g[i - 1][1]
*/