D. MEX Sequences

​​傳送門​​

題意：

思路：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int mod = 998244353;
ll vis[500010];
ll qpow(ll a,ll b)
{
  ll res = 1;
  while(b)
  {
    if(b&1)res = res*a%mod;
    a = a*a%mod;
    b>>=1;
  }
  return res;
}
int a[500010];
ll dp[500010][2];

int main()
{
  int t;
  cin>>t;
  while(t--)
  {
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++)scanf("%d",&a[i]);
    int mex = 0;
    ll ans = 0;
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
      a[i]++;
      dp[a[i]][0] = (dp[a[i]-1][0]+dp[a[i]][0]*2%mod)%mod;
      if(a[i]>1)
      dp[a[i]][1] = (dp[a[i]][1]*2+dp[a[i]-2][0])%mod;
      else dp[a[i]][1] = dp[a[i]][1]*2%mod;
      dp[a[i]+2][1] = (dp[a[i]+2][1]*2)%mod;
    }
    for(int i = 1; i <= n+1; i++)
    ans = (ans+dp[i][0]+dp[i][1])%mod;
    cout<<ans<<endl;
    for(int i = 0; i <= n+3; i++)vis[a[i]] = 0,dp[i][0] = dp[i][1] = 0;
  }
}