Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int nmax = 200005, mod = 1e9 + 7;
- int p, t, n, k, v[nmax], dp[nmax], pos[30], pos2[nmax], cnt[nmax], sum[nmax];
- int main()
- {
- cin >> p >> t;
- while (t--)
- {
- cin >> n >> k;
- pos2[0] = 1;
- for (int i = 1; i <= n; ++i){
- pos2[i] = 1e9;
- string s;
- cin >> s;
- int sSize = s.size();
- for (int j = 0; j < sSize; ++j){
- if (s[j] == '1'){
- v[i] |= (1 << j);
- }
- }
- }
- for (int i = 0; i < k; ++i){
- pos[i] = 1e9;
- }
- for (int i = 1; i <= n; ++i){
- for (int j = 0; j < k; ++j){
- if ((v[i] >> j) & 1){
- pos[j] = i;
- }
- }
- int minim = 1e9;
- bool ok = true;
- for (int j = 0; j < k; ++j){
- if (pos[j] == 1e9){
- ok = false;
- break;
- }
- minim = min(minim, pos[j]);
- }
- if (ok == false){
- continue;
- }
- minim -= 1;
- if (minim == 0){
- dp[i] = 1;
- cnt[i] = 1;
- sum[i] = (1LL * cnt[i] + sum[i - 1]) % mod;
- if (pos2[1] == 1e9){
- pos2[1] = i;
- }
- continue;
- }
- dp[i] = 1 + dp[minim];
- if (pos2[dp[i]] == 1e9){
- pos2[dp[i]] = i;
- }
- if (dp[i] == 1){
- cnt[i] = 1;
- }
- else{
- int pp = pos2[dp[minim]];
- cnt[i] = (sum[minim] - sum[pp - 1] + mod) % mod;
- }
- sum[i] = (1LL * cnt[i] + sum[i - 1]) % mod;
- }
- if (p == 1)
- cout << dp[n] << "\n";
- else
- cout << cnt[n] << "\n";
- memset(dp, 0, sizeof dp);
- memset(v, 0, sizeof v);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement