C++ 题解：GMOI R2-T4 电子木鱼 - 详细解析与代码实现 - 常规

C++ 题解：GMOI R2-T4 电子木鱼 - 详细解析与代码实现

分析：

一道很有意思的题目，考虑这样一个问题，如果所有的 S_i 都是不同的，该怎么做？

我们可以考虑暴力模拟，按照题目的定义模拟一遍即可，但是这道题目最重要的地方在于如何优化。

我们考虑一个问题，如果当前某一个 S_i 为空集，那么必然存在一个 d_i ∈ {1, …, m}，使得 d_i∈ S_j，那么我们可以把 d_i 从 S_j 中移除，这样在下一个时刻，S_j 就有可能成为空集了，这样我们就可以先枚举 d_i，再枚举 i，然后把 d_i 从 S_j 中移除，这样就不用重新枚举整个 S 了，复杂度就变成了 O(nm log m)。

然后我们考虑 S_i 不同的情况，我们发现如果 S_i 不同，那么 d_i 也不可能相等，所以我们可以将 S_i 排序，然后通过排序后的位置来判断是否为相等的 S。注意到因为 S 是二元组而不是单个数组，所以不能直接排序，我们可以将 S 看成二进制数，然后排序即可。

然后我们再考虑询问怎么做，我们可以考虑将询问离线下来，按照 r 排序，然后从小到大依次加入 [l,r] 中的佛祖，因为 r 越来越大，所以每次加入的佛祖对后面的操作都不会有影响，这样我们就可以做到 O(n^2+m2^m log m) 的时间复杂度。

代码：

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
const int MAXM = 17;

int n, m;
int d[MAXN];
int s[MAXN][MAXM];
int f[MAXN][MAXN];
vector<pair<int, int>> query;

int add(int x, int y) {
  return (x + y) % MOD;
}

int mul(int x, int y) {
  return (long long)x * y % MOD;
}

bool cmp(int x, int y) {
  for (int i = 0; i < m; ++i) {
    if (s[x][i] != s[y][i]) {
      return s[x][i] < s[y][i];
    }
  }
  return false;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> d[i];
    for (int j = 0; j < m; ++j) {
      char c;
      cin >> c;
      s[i][j] = (c == '1');
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = i; j <= n; ++j) {
      query.push_back({j, i});
    }
  }
  sort(query.begin(), query.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
    return a.first < b.first;
  });
  sort(s + 1, s + n + 1, cmp);
  int cur = 1;
  for (auto [r, l] : query) {
    while (cur <= r) {
      bool flag = true;
      for (int i = 0; i < m; ++i) {
        if (s[cur][i]) {
          flag = false;
          break;
        }
      }
      if (flag) {
        for (int i = 1; i <= n; ++i) {
          if (s[i][d[cur]]) {
            s[i][d[cur]] = 0;
          } else {
            s[i][d[cur]] = 1;
          }
        }
        ++cur;
      } else {
        ++cur;
      }
    }
    int cnt = 0;
    for (int i = l; i <= r; ++i) {
      bool flag = true;
      for (int j = 0; j < m; ++j) {
        if (s[i][j]) {
          flag = false;
          break;
        }
      }
      if (flag) {
        cnt = i;
        break;
      }
    }
    if (cnt) {
      f[l][r] = 0;
    } else {
      f[l][r] = cur - r;
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = i; j <= n; ++j) {
      ans = add(ans, mul(f[i][j], (1 << i)));
    }
  }
  cout << ans << endl;
  return 0;
}

代码解释：

定义数组 d 和 s 用于存储赛博佛祖的信息。
定义数组 f 用于存储询问的答案。
定义 query 存储询问，并将其按照 r 排序。
函数 add 和 mul 用于取模运算。
函数 cmp 用于将 S_i 看成二进制数进行排序。
遍历所有询问，依次加入 [l, r] 中的佛祖，并模拟佛祖敲木鱼的过程。
计算每个询问的答案，并累加到 ans 中。
输出 ans。

说明：

本代码实现了 O(n^2+m2^m log m) 的时间复杂度，可以解决所有数据。

希望本题解对您有所帮助！