Atcoder abc294

發表於 2023-05-31 更新於 2024-10-23 分類於 Atcoder ， ABC Disqus：文章字數： 1.9k 所需閱讀時間 ≈ 6 分鐘

Ex(子集DP,容斥原理)

https://atcoder.jp/contests/abc294/tasks

Ex - K-Coloring

n点无向图

m 边

点赋值 [1,k] 相邻点值不同的方案数 mod 998244353

n 30

m [0,30]

k 1e9

1024mb

我的思路

m 30, n 30, 想到的30相关的就是2^{30/2} 的meet-in-the-middle, 但没什么具体的想法

方案统计

对于一个具体方案，考虑按照点的index顺序从小到大交换

例如 1染色x , u染色1, 那么把所有x和1染色的交换成1和x, 那么得到的依然合法

这样 index顺序虫小到大染色c个的方案数 f(c)

ans = sum f(c) A(Permutation)(k,c)

dfs(u, cntcolor){
  color[u] = [1..cntcolor+1] and !=color[v in connect[u]]
  dfs(u+1, max(cntcolor,color[u]);
}

感觉复杂度会爆炸?吧?

不同难搞，要不然就是反过来容斥相同

属性i = 边i连的两点颜色相同

ans = sum (-1)^count(属性…) g(属性…)

这个问题就是 $2^{30}$太大, 需要拆分

右侧的g()=k^{未连通块个数}

题解

独立集 indepenedent set: 顶点集合，集合中顶点两两不相邻

如果$n$比较小

$s(i) =$ 恰好i种颜色的染色方案数

ans $=\sum_{i=1}^N \binom{K}{i} s(i)$

枚举s(1..n)的话,用 abc213G的 subset dp,需要$O(n3^n)$

subset dp 可以用子集卷积优化

$(f \ast g)(S) = \sum_{T \subseteq S} f(T) g(S \setminus T).$

原始需要$O(3^N)$, 子集dp 需要调用n次

可以优化到 $O(n^2 2^N)$

F(S) = int(bool(S 是一个非空独立集合 non-empty indepenedent set))

$f^K$ 为$F(S)$的K次卷积, $f^n(S)$的意义: 就是每个独立集(非空)一个颜色，因为是独立集所以里面的点两两不相邻，n次卷积就是n种颜色

$V$是顶点集合

ans $=\left(\sum_{i=1}^{\min(K, N)} \binom{K}{i} f^i \right)(V)$ )(这里官方题解幂次写错了)

注意到(如果 $n = 0$ 或者 $n\ge 0$)时 $f^n(S) = 0$, 所以, 可以修改求和的上下界

ans $=\left(\sum_{i=0}^K \binom{K}{i} f^i\right)(V).$

如果让$g(S) =$ bool(S是否为独立集合(可为空)), 则表达式$=g^K(V)$ 表示的就是小于等于k个独立集合的染色方案, 也= ans

如果$m$比较小

容斥原理, 对于边集$E$的子集合$P$, 计算

$\sum_{P \subseteq E} (-1)^{|P|} K^{k(V, P)}.$ 幂次就是上面的在指定边集$P$以后的连通块数量

复杂度$O(N2^M)$

$F(G) =$, 图$G$颜色$K$的方案数

$F(G) = F(G去掉边e(不去掉点)) - F(G把e两点合并)$ (其实就是是否选e,对应上面把容斥的(-1)展开)

如果$G$有独立点$v$, $F(G)=KF(G去掉v)$, 相当于处理孤立点(这里官方题解又写错了, denotes a removal of a vertex)

如果$G$有度为1的点, $F(G)=(K-1)F(G去掉v)$

对于度为$2$的点$u$,设它相连的边$e_1,e_2$

$F(G)=F(G去掉e_1去掉e_2)-F(G去掉e_1选中e_2)-F(G选中e_1去掉e_2)+F(G选中e_1选中e_2)$

$=KF(G去掉u)-F(G去掉u)-F(G去掉u)+F(G选中e_1选中e_2)$

$=(K-2)F(G去掉u)+F(G选中e_1选中e_2)$

注意到这里是少两条边，同时状态分叉两个, 所以总状态会分叉到约$2^{M/2}$个

如果所有点度数都大于3, 则被连的点$\le (2M/3)$, 用点比较少的方法

如果继续考虑度=3 的情况, 那么被连的点$\le (2M/4)$，就可以subset dp ($3^{15}=14348907$)

而度=3的情况$-$表示不选,$+$表示选

$F(G) = F(-e_0-e_1-e_2)-F(-e_0-e_1+e_2)-F(-e_0+e_1-e_2)+F(-e_0+e_1+e_2)-F(+e_0-e_1-e_2)+F(+e_0-e_1+e_2)+F(+e_0+e_1-e_2)-F(+e_0+e_1+e_2)$
$= KF(-u)-3F(-u)+F(-e_0+e_1+e_2)+F(+e_0-e_1+e_2)+F(+e_0+e_1-e_2)-F(+e_0+e_1+e_2)$
$= (K-3)F(-u)+F(-e_0+e_1+e_2)+F(+e_0-e_1+e_2)+F(+e_0+e_1-e_2)-F(+e_0+e_1+e_2)$

分叉 $5^{M/3}$, $5^{10}=9765625$

代码

#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}

mint calc1(int N, int K, vector<pair<int, int>> uv) { // 所有点的度 >= 4
  assert(N <= 15); // 2M/4
  vector<int> f(1 << N, 1); // f[vertex mask] = 是否是非空 独立集
  vector<int> adj(N); // bitmask 邻接表
  for (auto& [u, v] : uv) {
    adj[u] |= (1 << v);
    adj[v] |= (1 << u);
  }
  rep(msk,1,1<<N) rep(j,0,N) if ((msk >> j) & 1) f[msk] &= !(msk & adj[j]); // j 相邻的不在msk中

  vector<mint> dp(1 << N, 0); // dp[vertex mask] = 染色mask <= K的方案数
                              // dp[c]=f^c=convolution(dp[c-1],f)
  dp[0] = 1;
  mint ans = 0;
  mint bin = 1; // binom(K,c)
  rep(c,1,N+1){ // 颜色种数c
    vector<mint> ndp(1 << N);
    // 子集遍历O(3^N)
    rep(msk,0,1<<N) for(int j=msk;j;j=(j-1)&msk) ndp[msk] += dp[msk-j] * f[j];
    swap(dp, ndp);
    bin *= (K + 1 - c);
    bin /= c;
    ans += dp.back() * bin; // binom(K,c) (f^c)(1<<N)
  }
  return ans;
}

mint calc(int N, int K, vector<pair<int, int>> uv) { // 去掉度 <= 3 的点
  for (auto& [u, v] : uv) if (u == v) return 0;
  if (N == 0) return 1; // 空集
  for (auto& [u, v] : uv) if (u > v) swap(u,v); // 为了去重边
  sort(begin(uv), end(uv));
  uv.erase(unique(begin(uv), end(uv)), end(uv));
  auto ch = [&](int u, int v) { for (auto& [a, b] : uv) { // 交换点 u,v
    if (a == u or a == v) a = u + v - a;
    if (b == u or b == v) b = u + v - b;
  } };
  auto merge = [&](int u, int v) { for (auto& [a, b] : uv) { // 把所有 u 换成 v
    if (a == u) a = v;
    if (b == u) b = v;
  } };

  vector<int> deg(N);
  for (auto& [u, v] : uv) {
    deg[u]++;
    deg[v]++;
  }
  ch(min_element(begin(deg), end(deg)) - begin(deg), N - 1); // 交换 度最小的点 和 最后的点
  int mindeg = *min_element(begin(deg), end(deg));
  if (mindeg > 3) return calc1(N, K, uv); // 所有度都 > 3

  vector<int> adj;
  rep(_,0,mindeg) rep(j,0,size(uv)) { // 每次找到和 最后点(N-1) 相连的一条边删除
    auto [u,v] = uv[j];
    if (u == N-1 or v == N-1) {
      adj.push_back(u+v-(N-1)); // 相连的另外一个点
      uv.erase(begin(uv) + j);
      break;
    }
  }
  sort(begin(adj), end(adj)); // 和最小度的点相邻点
  rep(i,0,size(adj)) ch(adj[size(adj)-1-i],N-2-i); // 和最小度的点相邻点换到末尾(注意顺序是必要的
  mint ans = calc(N - 1, K, uv) * (K - mindeg); // 0,1,2,3 时 不选所有边的情况
  if (mindeg == 2) {
    merge(N-2,N-3);
    ans += calc(N - 2, K, uv); // 把和u相连的点合并成一个点(N-3), 移除u和被合并的
  } else if (mindeg == 3) {
    rep(_,0,3){ // 选两个边
      auto old = uv; // backup
      merge(N-2,N-3); // 每次 合并两个
      ans += calc(N - 2, K, uv);
      uv = old; // load backup
      ch(N - 3, N - 4); // 轮换 N-2,N-3,N-4
      ch(N - 2, N - 3);
    }
    merge(N-2,N-4);
    merge(N-3,N-4);
    ans -= calc(N - 3, K, uv);
  }
  return ans;
}
int main() {
  int N=read();
  int M=read();
  int K=read();
  vector<pair<int, int>> uv;
  rep(i,0,M) uv.push_back({read()-1,read()-1});
  printf("%d\n", calc(N, K, uv).val());
}