Advertisement
strawhat_8502

Untitled

Jul 5th, 2022
1,189
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. /*--------------AUTHOR : LANGAOP----------- */
  3.  
  4. #include<bits/stdc++.h>
  5. #include<iostream>
  6. #include<iomanip>
  7. #include<vector>
  8. #include<string>
  9. #include<math.h>
  10. #include<map>
  11. #include<algorithm>
  12. #include<set>
  13. #include<unordered_map>
  14. #include <unordered_set>
  15. #define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
  16. using namespace std;
  17.  
  18.  
  19.  
  20. #define ff first
  21. #define ss second
  22. #define pb push_back
  23. #define int long long int
  24. typedef long double lld;
  25. #define FOR(i,n) for(int i=0;i<n;i++)
  26. #define yes cout<<"YES"<<endl;
  27. #define no cout<<"NO"<<endl;
  28. #define MOD 1000000007
  29.  
  30. #define vi vector<int>
  31. #define pii pair<int, int>
  32. #define vii vector<pii>
  33. #define fr front()
  34. #define bk back()
  35. #define all(x) (x).begin(), (x).end()
  36. #define rall(x) (x).rbegin(), (x).rend()
  37.  
  38. typedef vector<char> vc;
  39. typedef vector<string> vs;
  40. typedef vector<pair<int, int> > vpii;
  41. typedef unordered_set<int> us;
  42. typedef map<int,int> mp;
  43.  
  44. //debugging
  45.  
  46. #ifndef ONLINE_JUDGE
  47. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  48. #else
  49. #define debug(x)
  50. #endif
  51.  
  52. void _print(int t) {cerr << t;}
  53. void _print(string t) {cerr << t;}
  54. void _print(char t) {cerr << t;}
  55. void _print(lld t) {cerr << t;}
  56. void _print(double t) {cerr << t;}
  57.  
  58. template <class T, class V> void _print(pair <T, V> p);
  59. template <class T> void _print(vector <T> v);
  60. template <class T> void _print(set <T> v);
  61. template <class T, class V> void _print(map <T, V> v);
  62. template <class T> void _print(multiset <T> v);
  63. template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
  64. template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  65. template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  66. template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  67. template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  68. template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  69.  
  70.  
  71. //Constants
  72. const long double pi= 3.141592653589793238;
  73. const int INF= 1e18;
  74. const int mod=1e9+7;
  75.  
  76. //MATHEMATICAL FUNCTIONS
  77.  
  78. int gcd(int a, int b){if (b == 0)return a;return gcd(b, a % b);} //gcd
  79. int lcm(int a, int b){return (a/gcd(a,b)*b);} //lcm
  80. //sieve
  81. vector<int> sieve(int n) {int*arr = new int[n + 1](); vector<int> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
  82.  
  83. //binary exponentation
  84. int expo(int a, int b, int mod) {int res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
  85.  
  86. //CHECK
  87.  
  88. bool isprime(int n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
  89. bool ispoweroftwo(int n){if(n==0)return false;return (ceil(log2(n)) == floor(log2(n)));}
  90. bool isperfectsquare(int x){if (x >= 0) {int sr = sqrt(x);return (sr * sr == x);}return false;}
  91. int ceils(int x, int y) {return x / y + (x % y > 0);}
  92.  
  93.  
  94. // Operator overloads
  95. template<typename T1, typename T2> // cin >> pair<T1, T2>
  96. istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }
  97. template<typename T> // cin >> vector<T>
  98. istream& operator>>(istream &istream, vector<T> &v){for (auto &it : v)cin >> it;return istream;}
  99. template<typename T1, typename T2> // cout << pair<T1, T2>
  100. ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); }
  101. template<typename T> // cout << vector<T>
  102. ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }
  103.  
  104. //USEFUL
  105. void printarr(int arr[], int n){FOR(i,n) cout << arr[i] << " ";cout << "\n";}
  106.  
  107. void solve(){
  108.     int n,m;
  109.     cin>>n>>m;
  110.     vi v(n);
  111.     cin>>v;
  112.     vector<vector<int> > dp(m+1,vector<int> (n,0));
  113.     for(int i=0;i<n;i++){
  114.         if(i==0){
  115.             if(v[i]!=0){
  116.                 dp[v[i]][i]=1;
  117.             }
  118.             else{
  119.                 for(int j=1;j<=m;j++){
  120.                     dp[j][i]=1;
  121.                 }
  122.             }
  123.         }
  124.         else{
  125.             if(v[i]!=0){
  126.                 dp[v[i]][i]+=(dp[v[i]][i-1]%mod+dp[v[i]-1][i-1]%mod)%mod;
  127.                 if(v[i]+1<=m){
  128.                     dp[v[i]][i]+=(dp[v[i]+1][i-1])%mod;
  129.                 }
  130.             }
  131.             else{
  132.                 for(int j=1;j<=m;j++){
  133.                     dp[j][i]=(dp[j-1][i-1]%mod+dp[j][i-1]%mod)%mod;
  134.                     if(j<m){
  135.                         dp[j][i]+=(dp[j+1][i-1]%mod)%mod;
  136.                     }
  137.                     dp[j][i]%=mod;
  138.                 }
  139.             }
  140.         }
  141.     }
  142.     debug(dp);
  143.     if(v[n-1]!=0){
  144.         cout<<dp[v[n-1]][v[n-1]];
  145.     }
  146.     else{
  147.         int res=0;
  148.         for(int j=1;j<=m;j++){
  149.             debug(dp[j][n-1]);
  150.             res=(res%mod+dp[j][n-1]%mod)%mod;
  151.             // res=(res%mod+dp[j][n-1]%mod)%mod;
  152.             debug(res);
  153.         }
  154.         debug(res);
  155.         cout<<res<<endl;
  156.     }    
  157. }
  158.  
  159. int32_t main()
  160. {
  161.     fast;
  162. //      #ifndef ONLINE_JUDGE
  163. //     freopen("input.txt", "r", stdin);
  164. //     freopen("output.txt", "w", stdout);
  165. // #endif
  166.    
  167.     int t;
  168.     t=1;
  169.     // cin>>t;
  170.     while(t--){
  171.  
  172.         // cout<<t;
  173.         solve();
  174.     }
  175.     return 0;
  176.    
  177. }
Advertisement
RAW Paste Data Copied
Advertisement