思路
拿到这道题，第一时间肯定想到是 \(dp\) 题目。
朴素 DP
用 \(dp_i\) 表示序列和为 \(i\) 的序列个数。因为原数组由奇数组成，所以 \(dp\) 只可能由 \(dp_{i-1}\)，\(dp_{i-3}\) 等等转移过来，若 \(i\in A\)，\(dp_i=0\)。即：
\[dp_i=\begin{cases} 0&i\in A\\ dp_{i-1}+dp_{i-3}+\cdots &otherwise \end{cases} \]优化
设 \(sum_i=f_i+f_{i-2}+f_{i-4}+\cdots\)。则 $f_i=sum_{i-1} \(，\)s_i=s_{i-2}+f_i$。
观察式子发现可以使用矩阵优化递推，我们维护 \(f_i\)，\(sum_{i-1}\)，\(sum_{i-2}\) 的值。
因为 ：
\[\left\{\begin{matrix} f_{i+1}=f_i+s_{i-2}\\ s_{i}=f_{i}+s_{i-2}\\ s_{i-2}=s_{i-2} \end{matrix}\right. \]所以可以构造如下矩阵：
\[\begin{bmatrix} f_i & s_{i-1} &s_{i-2} \end{bmatrix} \begin{bmatrix} 1 & 1 &0 \\ 0 & 0 & 1\\ 1 & 1&0 \end{bmatrix} \]所以之后分段快速幂即可，剩下的看我代码吧。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3, mod=998244353;
int a[100010];
struct mat {
int a[maxn+1][maxn+1];
mat() {
memset(a,0,sizeof(a));
}
mat operator*(const mat&T) const {
mat res;
for(int i=1;i<=maxn;i++) {
for(int j=1;j<=maxn;j++) {
for(int k=1;k<=maxn;k++) {
res.a[i][j]=(res.a[i][j]+a[i][k]*T.a[k][j])%mod;
}
}
}
return res;
}
mat operator^(int x) const {
mat bas,res;
for(int i=1;i<=maxn;i++) res.a[i][i]=1;
for(int i=1;i<=maxn;i++) {
for(int j=1;j<=maxn;j++) {
bas.a[i][j]=a[i][j]%mod;
}
}
while(x) {
if(x&1) {
res=res*bas;
}
bas=bas*bas;
x>>=1;
}
return res;
}
};
mat x,y,tmp;
signed main() {
x.a[1][1]=1, x.a[1][2]=0,x.a[1][3]=0;
int n,s;
cin>>n>>s;
y.a[1][1]=y.a[1][2]=y.a[2][3]=y.a[3][2]=y.a[3][1]=1;
for(int i=1;i<=n;i++) {
cin>>a[i];
tmp=y^(a[i]-a[i-1]);
x=x*tmp;
x.a[1][1]=0;
}
mat tmp=y^(s-a[n]);
x=x*tmp;
cout<<x.a[1][1];
return 0;
}