Mradul_22

Untitled

Sep 26th, 2024 (edited)
32
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.66 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Buildup() ios::sync_with_stdio(false),cin.tie(nullptr)
  4.  
  5. #define make_unique(x) (x).resize(unique(all((x)))-(x).begin())
  6. #define rotate(x,k) rotate(x.begin(),x.begin()+k,x.end());
  7. #define all(x) (x).begin(),(x).end()
  8. #define allr(x) (x).rbegin(),(x).rend()
  9. #define ceil(x,y) (x+y-1)/(y)
  10. #define sz(x) (int)(x).size()
  11. #define PI 3.141592653589793238
  12. #define ld long double
  13. #define ull unsigned long long
  14. #define ll long long
  15. #define nl '\n'
  16. #define ff first
  17. #define ss second
  18. #define IM INT_MAX
  19. #define IN INT_MIN
  20. #define LM LLONG_MAX
  21. #define LN LLONG_MIN
  22. #define pb push_back
  23. #define pp pop_back
  24. #define ins insert
  25. #define lb lower_bound
  26. #define ub upper_bound
  27.  
  28. #define Nl '\n'
  29. #define itn int
  30.  
  31. // const int M = 998244353;
  32. const int M = 1e9+7;
  33. // const int N = 2e5+5;
  34. // const int N = 1e5+5;
  35.  
  36. constexpr int inf = 1E9;
  37.  
  38. #ifndef ONLINE_JUDGE
  39. #define dbg(x...) cerr << #x << " : ["; _print(x)
  40. #else
  41. #define dbg(x...)
  42. #endif
  43.  
  44. void __print(int x) {cerr << x;}
  45. void __print(long x) {cerr << x;}
  46. void __print(ll x) {cerr << x;}
  47. void __print(ull x) {cerr << x;}
  48. void __print(ld x) {cerr << x;}
  49. void __print(float x) {cerr << x;}
  50. void __print(double x) {cerr << x;}
  51. void __print(char x) {cerr << '\'' << x << '\'';}
  52. void __print(const char *x) {cerr << '\"' << x << '\"';}
  53. void __print(const string &x) {cerr << '\"' << x << '\"';}
  54. void __print(bool x) {cerr << (x ? "T" : "F");}
  55.  
  56. template<typename T, typename V>
  57. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.ff); cerr << ','; __print(x.ss); cerr << '}';}
  58. template<typename T>
  59. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  60. void _print() {cerr << "]\n";}
  61. void __print(vector<bool> &v) {int f = 0; cerr << '{'; for (auto &&i : v) cerr << (f++ ? "," : "") << (i ? "T" : "F"); cerr << "}";}
  62. template <typename T, typename... V>
  63. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  64. template <size_t N> void __print(bitset<N> x) {cerr << x;}
  65.  
  66.  
  67. /* .....!! Start by doing what's necessary; then do what's possible;
  68. and suddenly you are doing impossible !!..... */
  69.  
  70. int main(){
  71. #ifndef ONLINE_JUDGE
  72. freopen("errorf.in", "w", stderr);
  73. #endif
  74.  
  75. Buildup();
  76.  
  77. int ___ = 1;
  78. // cin >> ___;
  79.  
  80. while(___--){
  81.  
  82. int n,m;
  83. cin>>n>>m;
  84.  
  85. vector<int> v(n);
  86. for(auto &it : v) cin>>it;
  87.  
  88. vector<int> dp(m+2);
  89. for(int i=0; i<n; i++){
  90. auto ndp = dp;
  91. for(int j=1; j<=m; j++){
  92. if(!i){
  93. if(!v[i]){
  94. ndp.assign(m+2,1);
  95. ndp.front() = ndp.back() = 0;
  96. }
  97. else ndp[v[i]] = 1;
  98. }
  99. else if(v[i]){
  100. ndp.assign(m+2,0);
  101. (ndp[v[i]] += dp[v[i]-1]) %= M;
  102. (ndp[v[i]] += dp[v[i]]) %= M;
  103. (ndp[v[i]] += dp[v[i]+1]) %= M;
  104. }
  105. else{
  106. (ndp[j] += dp[j-1]) %= M;
  107. (ndp[j] += dp[j]) %= M;
  108. (ndp[j] += dp[j+1]) %= M;
  109. }
  110. }
  111. dp = ndp;
  112. }
  113.  
  114. for(int i=1; i<=m; i++) (dp[i] += dp[i-1]) %= M;
  115. cout<<dp[m]<<nl;
  116. // int ans = 0;
  117. // for(auto &x : dp) (ans += x) %= M;
  118. // dbg(dp);
  119.  
  120. }
  121.  
  122. }
Advertisement
Add Comment
Please, Sign In to add comment