牛客OI周赛15-普及组-C-区间加

我觉得超详细了？？？
题解：
我们先来考虑一下什么情况下，答案会为0。
(1),你都比m大了还加个鬼啊
(2)，因为包含的区间的起点最多只能包含各一次
(3),因为包含的区间结束位置最多只能为各一次。
(4),因为包含的区间若有个，必然至少有个区间包含，包含的区间同理
--
除了以上4种情况外，接下来来解决其他情况。
直接上。 表示前个数加到的方案数，但这里需要修改一下区间加的合法性，把原先的对于任意两次区间加的起始，结束位置各不相同修改为对于任意区间的起始位置各不相同，除了以i结尾外，结束位置各不相同换句话说，就是允许多个以结尾的区间。显然遍历到时，以结尾的区间有个,如果我们先判断一下若则原题的答案变为0了，那么遍历到时，则我们修改的条件同时满足了原先的条件。那么答案便是了。
现在考虑状态转移：
（1）当时，,即把原先以结尾的区间都延迟到或新设区间和从原先个以结尾的区间选个出来延迟到。
（2）当时，,因为此时包含的区间比包含的区间多了一个，所以不能新设区间而要从原先的以结尾的区间选出来延长。
（3）当时，这个时候，以结尾的区间就都要延长啦。
至此结束，时间复杂度
代码：

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int MX=3e5+7;
const int mod=998244355;
using namespace std;
ll qpow(ll a,ll b,ll MOD=mod){for(ll ans=1;;a=a*a%MOD,b>>=1){if(b&1)ans=ans*a%MOD;if(!b)return ans;}}
ll inv(ll a,ll MOD=mod){return qpow(a,MOD-2,MOD);}
ll __gcm(ll a,ll b){return a*b/__gcd(a,b);}
ll dp[MX];
int a[MX];
int main()
{
  ios::sync_with_stdio(0),cin.tie(0);
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
      cin>>a[i];
  }
  ll ans=1;
  dp[1]=1;
  if(m-a[1]>1||a[1]>m){
    cout<<0<<endl;
    return 0;
  }
  for(int i=2;i<=n;i++)
  {
      if(m-a[i]>i||m<a[i]||(m-a[i]>(n-i+1)))
      {
          cout<<0<<endl;
          return 0;
      }
      if(a[i-1]-a[i]==1)
      {
          dp[i]=dp[i-1];
      }
      else if(a[i]-a[i-1]==1)
      {
          dp[i]=dp[i-1]*(m-a[i-1])%mod;
      }
      else if(a[i]==a[i-1])
      {
          dp[i]=(dp[i-1]+dp[i-1]*(m-a[i-1]))%mod;
      }
      else {
        cout<<0<<endl;
        return 0;
      }
     // cout<<dp[i]<<endl;
  }
  cout<<dp[n]<<endl;


}