竞赛图小记

· · 算法·理论

基本性质

首先竞赛图就是一个 n 个点，\frac{n(n-1)}{2} 条边的有向图，每个点对 (i,j),i\ne j 之间恰有一条有向边，可能是 i\to j 也可能是 j\to i。

竞赛图看起来有 O\left(n\right) 个性质，但是其实最关键的只有一个，就是竞赛图缩点之后是一条链。

这个链可以说是广义的链，因为除去主链之外的边都是不会改变连通性的边：

也就是说，缩点之后假如一条主链为 a_1\to a_2\to \cdots \to a_n，那么对于 i<j，都有边 a_i\to a_j，其他点对就不存在边。

为什么会是这样的一个结构呢？实际上很好理解，首先缩点之后的有向图就是一个 DAG。因为任意两点之间都有恰好一条边，而对于一个新点 i（对应原图中的一个强连通分量），如果存在点 j>i,j\to i，因为在链上 i 肯定可以到达 j，这里就构成了环，不符合 DAG。

仔细瞪一瞪 这个广义的链形态！

CF1498E. Two Houses (*2200)

竞赛图，给出了点的入度。问的是连通性问题，所以容易想到考虑缩点之后来做。实际上竞赛图的性质基本上都是在缩点之后体现出来的，所以碰到的时候考虑缩点一下可能会更容易发现大量性质！

缩点之后就得到了上面那样的一条链，我们考虑，因为询问出了一个 x\to y 之后就得立马给出答案了，也就是说我们得询问一对确保了 y\to x 的 (x,y)。那我们考虑，怎么根据给出的入度来确定一对 x\to y。如果两个点在同一个连通块内，那么肯定是可以双向到达的；否则我们考虑在这个缩了点的链上，x\to y 当且仅当 x 所在的强连通分量在 y 的前面，也就是说 B(x)\to B(y)，其中 B(x) 表示 x 所在的强连通分量编号。

比如图中的 1,3 两个块，有 1\to 3，我们考虑记每个块 u 的点数为 s_u，那么块 1 中的点的出度应该是 \ge s_2+s_3+s_4+s_5，而 3 中的点的出度 <s_3+s_4+s_5。也就是说，如果点 x,y 不在一个块中，且 out_x>out_y，那 x\to y 是肯定的。对于 x,y 同块的情况，out_x>out_y 的话，x\to y 也是肯定的。

也就是说，如果 out_x>out_y，x\to y 是一定满足的。由于输入的是入度，我们将 out_x=n-1-in_x 算出来即可。接下来我们枚举所有点对，将点对按照 |out_x-out_y| 降序遍历，如果 out_x\le out_y 且询问得出 x\to y，(x,y) 就是一个可行的答案。我们一直询问直到回答 Yes，否则回答 ! 0 0。

复杂度 O\left(n^2\log ^2n\right)。

tp HARUTO() {
   tp n; cin >> n;
   vector<tp> d(n + 1, 0);
   for (tp i = 1; i <= n; ++i) cin >> d[i], d[i] = n - 1 - d[i];
   vector<tuple<tp, tp, tp>> v;
   for (tp i = 1; i <= n; ++i) {
      for (tp j = i + 1; j <= n; ++j) {
         if (d[i] <= d[j]) v.emplace_back(d[j] - d[i], i, j);
         else v.emplace_back(d[i] - d[j], j, i);
      }
   }
   sort(FULL(v), greater<>());
   for (auto [p, x, y] : v) {
      cout << "? " << x << ' ' << y << endl;
      string c; cin >> c;
      if (c[0] == 'Y') return cout << "! " << x << ' ' << y << endl, 0; 
   }
   cout << "! 0 0" << endl;
   return 0;
}

CF804F. Fake bullions (*3400)

喜欢我们的难度 delta 吗？！

可以说是强行二合一，所以我们分两个部分来做：

求一个点的假金条数

我们考虑现在有两个点，满足 u\to v，他们上面的人的拿金条情况为 a_{u,0\sim s_u-1},a_{v,0\sim s_v-1}。什么样的 a_{u,i} 可以转移到 a_{v,j}？手玩一下，可以发现就是满足 s_ux+i=s_vy+j 的 (i,j)，容易解出 i\equiv j\pmod g, g = \gcd(s_u,s_v)。

于是我们可以维护一个数组 b，先将所有 a_{u,i}=1 都更新到 b_{i\bmod g}=1，然后对于 a_{v,j}=0，如果 b_{j\bmod g}=1，就可以把它变成 1，i 点的假金条数 +1。

如果直接暴力更新，我们发现因为图不是 DAG，会产生问题。于是我们考虑先缩点。一个强连通分量内，我们可以直接把所有点弄到 b 上面，这时候我们取 g 为强连通分量内所有的 s 的 \gcd，再用 b 更新 a。

缩点之后的竞赛图是一条链，我们只要保留一条贯穿所有连通块的从一个点开始的链就可以更新了，具体我们从链的起点开始，对于 u\to v，用 u 更新 v，维护方式同上，只是这时候取 g'=\gcd(g_u,g_v)。实际上如果不是竞赛图也可以在 DAG 上做拓扑排序做，但是好像得用 bitset 维护，这里复杂度正确只是因为每个点只要用于更新，被更新各 O\left(1\right) 次，且 \sum s_u\le 2\times 10^6。如果最终形态只是一个 DAG，暴力更新就不对了。可是我不知道这里怎么 bitset，不管了，不在本文讨论范围内！

现在我们就能够算出一个点上的真假金条分别的数量了。

统计最终的方案数

感觉这个部分有点小难想啊，想要不容斥并且统计得不重不漏还是需要一点技巧的。

我们容易想到，记 mn_i,mx_i 分别表示 i 点能卖出的最小/最大金条数，其中 mn_i 就是真金条数，mx_i 就是真假金条数总和。这个已经在前一问中可以算出了。

现在是非严格前 n_1 大选 n_2 个的问题，因为我们是对这 n_2 个选出来的数的集合计数，所以我们应该对这 n_2 个数来讨论。

我们钦定这 n_2 个选出来的数里 mx 最小的点为 i。如果 mx 相同我们取点标号更大的。在计数的时候，我们默认剩下的 n_2-1 个点都选了 mx 块金条，这是不会影响统计的，并且很方便比较。实际上我们也默认了 i 是选了 mx 块金条。

我们可以把除去 i 以外的“备选点”分为两类，一类是如果选择了 i 进入前 n_1 大就肯定会被选入 n_1 的点，数量我们记为 c_1；另一类是可以被选入 n_2 的点数 c_2。

对于一个点 j\ne i：

那么我们考虑枚举这 n_2 个点中 c_2 类点的个数 j，得满足 j+c_1+1\le n_1。然后这里带来的方案数就是，\binom{c_2}{j}\binom{c_1}{n_2-j-1}。这里很好理解，然后我们也不需要判断其他的条件了，因为剩下的都是关于 n_2 的限制，不满足的 j 会出现组合数变成 0 的情况，所以贡献不会变。

复杂度 O\left(n^2+\sum s_u\right)。

constexpr tp N = 5e3 + 5, M = 2e6 + 5;
array<tp, N> fac, ifc;

void QWQ() {
   //freopen(".in", "r", stdin), freopen(".out", "w", stdout);
   ios::sync_with_stdio(false), cin.tie(nullptr);
   tp n = 5e3;
   fac[0] = 1;
   for (tp i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
   ifc[n] = pow(fac[n], mod - 2);
   for (tp i = n - 1; ~i; --i) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;
   return ;
}
tp bn(tp n, tp m) {
   if (n < 0 || m < 0 || n < m) return 0;
   return 1ll * fac[n] * ifc[m] % mod * ifc[n - m] % mod;
}

tp n, n1, n2;
array<vector<tp>, N> e;
array<tp, N> s;
array<vector<bool>, N> a;
array<bool, M> b;

tp tot, cnt;
array<tp, N> dfn, low, bel, g, mn, mx;
array<bool, N> ins;
stack<tp> stk;
array<vector<tp>, N> scc;
void upd1(tp x, tp d) {
   for (auto u : scc[x])
      for (tp i = 0; i < s[u]; ++i) b[i % d] |= a[u][i];
   return ;
}
void upd2(tp x, tp d) {
   for (auto u : scc[x])
      for (tp i = 0; i < s[u]; ++i)
         if (b[i % d] && !a[u][i]) a[u][i] = 1, mx[u]++;
   return ;
}
void upd3(tp d) {
   for (tp i = 0; i < d; ++i) b[i] = 0;
   return ;
}

void tar(tp u) {
   dfn[u] = low[u] = ++tot;
   stk.emplace(u), ins[u] = 1;
   for (auto v : e[u]) {
      if (!dfn[v])
         tar(v), ckmin(low[u], low[v]);
      if (ins[v]) ckmin(low[u], dfn[v]); 
   }
   if (dfn[u] == low[u]) {
      ++cnt;
      while (1) {
         auto v = stk.top(); stk.pop(), ins[v] = 0;
         scc[cnt].emplace_back(v), bel[v] = cnt, g[cnt] = __gcd(g[cnt], s[v]);
         if (v == u) break;
      }
      upd1(cnt, g[cnt]), upd2(cnt, g[cnt]), upd3(g[cnt]);
   }
   return ;
}

array<tp, N> out;

tp HARUTO() {
   cin >> n >> n1 >> n2;
   for (tp i = 1; i <= n; ++i) {
      for (tp j = 1; j <= n; ++j) {
         char c; cin >> c;
         if (c == '1') e[i].emplace_back(j);
      }
   }
   for (tp i = 1; i <= n; ++i) {
      cin >> s[i], a[i].assign(s[i], 0);
      char c;
      for (tp j = 0; j < s[i]; ++j)
         cin >> c, a[i][j] = c - '0', mx[i] += a[i][j];
      mn[i] = mx[i];
   }
   for (tp i = 1; i <= n; ++i)
      if (!dfn[i]) tar(i);
   for (tp u = 1; u <= n; ++u)
      for (auto v : e[u])
         if (bel[u] != bel[v]) out[bel[u]]++;
   vector<tp> ord(tot + 1, 0);
   iota(ALL(ord, 1, tot), 1), sort(ALL(ord, 1, tot), [&](tp x, tp y) { return out[x] > out[y]; });
   for (tp i = 1; i < tot; ++i) {
      tp u = ord[i], v = ord[i + 1], d = __gcd(g[u], g[v]);
      upd1(u, d), upd2(v, d), upd3(d);
   }

   tp ans = 0;
   for (tp i = 1; i <= n; ++i) {
      tp c1 = 0, c2 = 0;
      for (tp j = 1; j <= n; ++j) {
         if (mn[j] > mx[i]) c1++;
         else if (mx[j] > mx[i] || (mx[j] == mx[i] && j < i)) c2++;
      }
      for (tp j = 0; j + c1 < n1; ++j)
         add(ans, 1ll * bn(c2, j) * bn(c1, n2 - j - 1) % mod);
   }
   cout << ans << "\n";
   return 0;
}

int main() {
   QWQ();
   tp t = 1;
   while (t--) HARUTO();
   return 0;
}

小结

相信大家看到这里，都能明白一件事，竞赛图的题目的难点其实不在于竞赛图的部分，而是在于利用了竞赛图缩点后的性质，在连通性问题上面之后的处理。而竞赛图的性质也可以说是和连通性问题捆绑了。

希望大家学会了这个 trick。