SHARE
TWEET

Untitled

a guest Apr 24th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. #include <string>
  6. #include <cmath>
  7. #include <set>
  8. #include <random>
  9. #define int long long
  10. #define debug(a) cout << #a << " = " << a << "\n"
  11.  
  12. using namespace std;
  13.  
  14. const int mod = 1e9 + 7;
  15.  
  16. void add(int &a, int b)
  17. {
  18.     a += b;
  19.     a %= mod;
  20. }
  21.  
  22. int mul(int a, int b)
  23. {
  24.     return (a * b) % mod;
  25. }
  26.  
  27. const int MAXN = 2e5 + 15;
  28. int dp[MAXN];
  29. int link[MAXN];
  30.  
  31. // DO
  32.  
  33. int t[4 * MAXN];
  34. int psh[4 * MAXN];
  35. void push(int i, int tl, int tr)
  36. {
  37.     add(t[i], mul(tr - tl, psh[i]));
  38.     if (tl + 1 != tr)
  39.     {
  40.         add(psh[i * 2], psh[i]);
  41.         add(psh[i * 2 + 1], psh[i]);
  42.     }
  43.     psh[i] = 0;
  44. }
  45.  
  46. void modify(int i, int tl, int tr, int l, int r, int key)
  47. {
  48.     push(i, tl, tr);
  49.     if (l <= tl && tr <= r)
  50.     {
  51.         add(psh[i], key);
  52.         push(i, tl, tr);
  53.         return;
  54.     }
  55.     if (tl >= r || l >= tr)
  56.     {
  57.         return;
  58.     }
  59.     int mid = (tl + tr) / 2;
  60.     modify(i * 2, tl, mid, l, r, key);
  61.     modify(i * 2 + 1, mid, tr, l, r, key);
  62.     t[i] = 0;
  63.     add(t[i], t[i * 2]);
  64.     add(t[i], t[i * 2 + 1]);
  65. }
  66.  
  67. int get(int i, int tl, int tr, int pos)
  68. {
  69.     push(i, tl, tr);
  70.     if (tl + 1 == tr)
  71.     {
  72.         return t[i];
  73.     }
  74.     int mid = (tl + tr) / 2;
  75.     if (pos < mid)
  76.         return get(i * 2, tl, mid, pos);
  77.     else
  78.         return get(i * 2 + 1, mid, tr, pos);
  79. }
  80.  
  81. //
  82.  
  83. string a[MAXN];
  84.  
  85. void solve()
  86. {
  87.     int n, k;
  88.     cin >> n >> k;
  89.     for (int i = 1; i <= n; ++i)
  90.     {
  91.         cin >> a[i];
  92.     }
  93.     dp[0] = 1;
  94.     int s = 0;
  95.     for (int i = n; i >= 1; --i)
  96.     {
  97.         link[i] = s;
  98.         if (a[i].size() != 3) s = 0;
  99.         else ++s;    
  100.     }
  101.     int cur = 0;
  102.     for (int i = 1; i <= n; ++i)
  103.     {
  104.         int sz = a[i].size();
  105.         if (a[i] == "0")
  106.         {
  107.             modify(1, 0, MAXN, i, i + 1, dp[i - 1]);
  108.         }
  109.         else
  110.         {
  111.             if (sz < 3 || (sz == 3 && a[i][0] != '0'))
  112.             {
  113.                 int r = (k - sz) / 3;
  114.                 int nex = i + min(r, link[i]);
  115.                 modify(1, 0, MAXN, i, nex + 1, dp[i - 1]);
  116.             }
  117.         }
  118.         dp[i] = get(1, 0, MAXN, i);
  119.     }
  120.     cout << dp[n] << "\n";
  121. }
  122.  
  123. signed main()
  124. {
  125.     ios::sync_with_stdio(false);
  126.     cin.tie(0);
  127. #ifndef ONLINE_JUDGE
  128.     freopen("input.txt", "r", stdin);
  129. #endif
  130.     solve();
  131.     return 0;
  132. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top