Advertisement
mihaimarcel21

Bob1

Apr 20th, 2021
517
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int nmax = 200005, mod = 1e9 + 7;
  6. int p, t, n, k, v[nmax], dp[nmax], pos[30], pos2[nmax], cnt[nmax], sum[nmax];
  7.  
  8. int main()
  9. {
  10.     cin >> p >> t;
  11.     while (t--)
  12.     {
  13.         cin >> n >> k;
  14.         pos2[0] = 1;
  15.         for (int i = 1; i <= n; ++i){
  16.             pos2[i] = 1e9;
  17.             string s;
  18.             cin >> s;
  19.             int sSize = s.size();
  20.             for (int j = 0; j < sSize; ++j){
  21.                 if (s[j] == '1'){
  22.                     v[i] |= (1 << j);
  23.                 }
  24.             }
  25.         }
  26.         for (int i = 0; i < k; ++i){
  27.             pos[i] = 1e9;
  28.         }
  29.         for (int i = 1; i <= n; ++i){
  30.             for (int j = 0; j < k; ++j){
  31.                 if ((v[i] >> j) & 1){
  32.                     pos[j] = i;
  33.                 }
  34.             }
  35.             int minim = 1e9;
  36.             bool ok = true;
  37.             for (int j = 0; j < k; ++j){
  38.                 if (pos[j] == 1e9){
  39.                     ok = false;
  40.                     break;
  41.                 }
  42.                 minim = min(minim, pos[j]);
  43.             }
  44.             if (ok == false){
  45.                 continue;
  46.             }
  47.             minim -= 1;
  48.             if (minim == 0){
  49.                 dp[i] = 1;
  50.                 cnt[i] = 1;
  51.                 sum[i] = (1LL * cnt[i] + sum[i - 1]) % mod;
  52.                 if (pos2[1] == 1e9){
  53.                     pos2[1] = i;
  54.                 }
  55.                 continue;
  56.             }
  57.             dp[i] = 1 + dp[minim];
  58.             if (pos2[dp[i]] == 1e9){
  59.                 pos2[dp[i]] = i;
  60.             }
  61.             if (dp[i] == 1){
  62.                 cnt[i] = 1;
  63.             }
  64.             else{
  65.                 int pp = pos2[dp[minim]];
  66.                 cnt[i] = (sum[minim] - sum[pp - 1] + mod) % mod;
  67.             }
  68.             sum[i] = (1LL * cnt[i] + sum[i - 1]) % mod;
  69.         }
  70.         if (p == 1)
  71.             cout << dp[n] << "\n";
  72.         else
  73.             cout << cnt[n] << "\n";
  74.         memset(dp, 0, sizeof dp);
  75.         memset(v, 0, sizeof v);
  76.     }
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement