题解：CF1466F Euclid's nightmare

· · 题解

前言：

之前 vp 过一场 ABC，做过一道思路上比较像的题。同样是一个集合，两个集合之间能够到达当且仅当集合中至少有一个数相同。显然我们可以把一个集合看成一个虚点，给集合之间连边。但是直接连边显然是不太行的，所以我们需要让数字作为中转点再做 dfs。

思路：

再回到这道题上。显然我们可以沿用连边的这个技巧。假如说某一个向量中有两个坐标为 1，那么我们就可以把这两个坐标对应的点连起来。当选了这条边的时候这两个数被选的次数就要加 1，也就是这两个点的度数加 1。那么我们就可以把向量的选和不选转化成图上边的选和不选。

那如果向量只有一个坐标为 1 要怎么办？那就把它转化成两个坐标为 1 的情况！我们可以新建一个虚点，假设为 m+1。我们把向量为 1 的坐标对应的那个点和 m+1 连边。显然 m+1 的情况是由其他向量被动决定的，所以这么做是没有问题的。

当我们把每个向量都这么处理完后会形成若干个联通块。现在考虑其中的一个联通块。显然我们并不能直接处理这个联通块，因为可能会出现不同的选边导致相同的情况。那我们考虑什么时候会出现相同的情况。 假如说红边为我们原本就选的边，黑边为不选的边，下面第一行数字为这个数被选的次数 \mod2。

现在我们要加入一条蓝边，那么这些数字出现的次数就变成第二行了。

但是我们可以找到另一种方法不用加这条边也可以达到同样的效果。 这说明假如你加入的这条边的两个点在同一个联通块内，那么这条边就可以不加。这个显然就是并查集了。假设这个并查集内有 sz_i 个点，那么就有 sz_i-1 调边。我们把一个联通块看成一棵树，那么从下往上，每一条边的选和不选都会导致最终每个点的状态不同，因此对于一个联通块总共有 2^{sz_i-1} 种不同的情况。假设有 cnt 个联通块，那么总共有 \prod_{i=1}^{cnt}2^{sz_i-1}=2^{\sum_{i=1}^{cnt}sz_i-1}。那哪些向量是我们要选的呢？显然我们在加边的时候就可以确定这些向量了。把我们选上的边所对应的向量加进去就行了。

code：

#include <iostream>
#include <algorithm>
#include <vector>

// using namespace std;

#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define REP(i, l, r)  for(int i = (l);i <= (r);i++)
#define DEP(i, r, l)  for(int i = (r);i >= (l);i--)

void read(){}
template<typename T1, typename ...T2>inline void read(T1 &x, T2 &...oth) {
  x = 0;
  int ch = getchar(), f = 0;
  while(ch < '0' or '9' < ch) {
    if (ch == '-') f = 1;
    ch = getchar();
  }
  while('0' <= ch and ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  if(f) x = -x;
  read(oth...);
  return;
}

namespace YZLK{
  const int N = 5e5 + 10;
  const int M = 1e6 + 10;
  const int mod = 1e9 + 7;
  int n, m, tot;
  int pw[N];
  std::vector<int> ve[N];
  void init() {
    pw[0] = 1;
    REP(i, 1, N - 10) pw[i] = pw[i - 1] * 2 % mod;
    return;
  }
  std::vector<int> ans;
  struct dsu{
    int fa[M], sz[M];
    void init(int x) {
      REP(i, 0, x + 1)  fa[i] = i, sz[i] = 1;
    }
    int find(int x) {
      return (x == fa[x] ? fa[x] : fa[x] = find(fa[x]));
    }
    bool merge(int u, int v) {
      int x = find(u), y = find(v);
      if (x == y) return 0;
      if (sz[x] > sz[y])  std::swap(x, y);
      fa[x] = y;
      sz[y] += sz[x];
      return 1;
    }
  }d;

    void main() {
    init();
    read(n, m);
    tot = m + 1;
    d.init(M - 10);
    REP(i, 1, n) {
      int ln, x;
      read(ln);
      REP(j, 1, ln) {
        read(x);
        ve[i].pb(x);
      }
      if (ln == 1)  ve[i].pb(tot);
      if (d.merge(ve[i][0], ve[i][1]))  ans.pb(i);
    }

    std::cout << pw[ans.size()] << " " << ans.size() << "\n";
    for(auto it:ans)  std::cout << it << " ";
    puts("");
    return;
  }
}

signed main() {
//   freopen("knapsack.in", "r", stdin);
//   freopen("knapsack.out", "w", stdout);

  // cin.tie(nullptr) -> sync_with_stdio(false);
  int T = 1;
  // read(T);
  while(T--) {
    YZLK::main();
  }

  // fclose(stdin);
  // fclose(stdout);

  return 0;
}