Atcoder abc253

發表於 更新於 分類於 ， Disqus： 文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘
Ex(基尔霍夫定律,DP)

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

Ex - We Love Forest

一个n点0边的图 G

给序列u[1..m], v[1..m]

做k次操作

每次1~m中等概率选i, 连接ui,vi, (允许重边, 没有自环

对于k = 1…n-1

计算 图是森林的概率

mod 998244353

n 14

m 500

2s

1024mb

我的思路

n 这么小

问题其实就是说k次选择没有出现重边, 也没有产生环的概率

如果只是重边 还很好做, 但是问题是如何判断没有环的概率

然后说 有没有把并查集状态 全部表示出来, 但这样看似乎n又很大

f(x) = x个点的并查集状态的数

考虑和其中最小点1在一起的点数

f(x) = sum binom(x,i) f(x-1-i), i = 0..x-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = 15
a = [0 for i in range(n)]
a[0] = 1

fac = [1 for i in range(n)]
for i in range(1,n):
    fac[i] = fac[i-1]*i
def binom(n,m):
    return fac[n]//fac[n-m]//fac[m]

for i in range(1,n):
    for j in range(i):
        a[i] += binom(i-1,j) * a[i-1-j]
    print(i,a[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1 1
2 2
3 5
4 15
5 52
6 203
7 877
8 4140
9 21147
10 115975
11 678570
12 4213597
13 27644437
14 190899322

状态数量接受不了, 更别提转移代价了

但是如果 容斥看 指定一个mask中的点构成树, 其余任意的话, 能否容斥

并想不出 容斥的单独属性

除非是 每个mask中是森林, 但是既然都是森林了不如直接算出答案

如果每个mask是树, 所有的并交没有意义?

题解

基尔霍夫定律: 一个图G的生成树个数 = G的n-1阶 代数余子式

bit dp

f(mask) = 点集为mask的 生成树 的个数

g(mask,i) = 点集为mask的 森林(且 选中了 i条边) 的个数

状态是 n2^n 的

那么 ans[k] = (g((1 << n)-1,k) / (m^k))

f(mask) 可以 枚举子集(2^n) * 计算行列式(n^3) 算出

g(mask,i) 类似于 abc213g 中dp的想法 通过讨论集合中和点1的属于同一个树(连通块)的情况来算转移

令u(mask) = mask中最小点

$g(S,i) = \sum_{u(S) \in T \subset S} f(T) * g(S-T,i-(|T|-1|))$

即 = 与点u的构成树 * 剩下的点构成森林

无用脑洞

我对三行四列行列式有点脑洞

感觉跟着 Binet-Cauchy 定理的话

其实可以发现它可以提出来binom(4,3)个数, 并不需要12个数表示, 所以记作 X_{3,4} (v0,v1,v2,v3) 里面的数有序,按照排列的顺序

但是可能不少情况 binom(max(m,n),min(m,n)) 比 nm 还多

n>=m时

X_{m,n} * X_{n,m} = X_{m,m} (对应位置乘积之和)

n < m时,

X_{m,n} * X_{n,m} = X_{n,n} (0)

看起来很美好,但实际上

[1,0;0,1] 和 [0,1;-1,0] 的上述表示一致

但是 (1,2) 去乘一个得到(1,2) 一个得到(2,-1) 都不一样

所以这个脑洞显然并没什么卵用

代码

https://atcoder.jp/contests/abc253/submissions/35519263

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
#define rep(i,a,n) for(int i=a;i<(int)(n);i++)
#define per(i,a,n) for(int i=n;i-->(int)(a);)
int read(){int r;scanf("%d",&r);return r;}
template<class T>
T det(vector<vector<T>>& a){ // 高斯消元
  auto n=a.size();
  if(n==0)return 1;
  assert(n==a[0].size());
  T ans=1;
  T neg=-1; // 除法慢 少用除法
  rep(j,0,n){
    rep(i,j,n)if(a[i][j]!=0){ // >=j行中找j列首个非零值,做行交换
      if(i!=j){
        std::swap(a[i],a[j]);
        ans*=neg;
      }
      break;
    }
    ans*=a[j][j];// 主元
    if(ans==0)return 0;
    T t=T(1)/a[j][j]; // 少做除法
    rep(k,j,n)a[j][k]*=t;
    rep(i,j+1,n)per(k,j,n)a[i][k]-=a[i][j]*a[j][k]; // 行变换, 注意per顺序
  }
  return ans;
}

// Ex
const int N=14;
mint fac[N+1]={1};
mint f[1<<N];// f[mask]=mask中的点的生成树个数
mint g[1<<N][N]={{1}}; // g[0][0]=1; f[mask][i]=mask中的点选了i条边的森林个数
int c[1<<N];// bit count
int e[N][N];
int n;

int main(){
  n = read();
  rep(i,1,n+1)fac[i]=fac[i-1]*i;
  rep(S,1,1<<n)c[S]=c[S&(S-1)]+1;
  int m = read();
  rep(_,0,m){
    int u = read()-1;
    int v = read()-1;
    e[u][v]+=1;
    e[v][u]+=1;
  }
  // f
  rep(S,1,1<<n){
    auto A=vector(c[S]-1,vector<mint>(c[S]-1,0)); // 忽略第一行第一列
    int ni=-1;
    rep(i,0,n)if(S&(1<<i)){
      int nj=ni+1;
      rep(j,i+1,n)if(S&(1<<j)){
        int d=e[i][j];
        if(~ni)A[ni][ni]+=d;
        if(~nj)A[nj][nj]+=d;
        if(~ni&&~nj)A[ni][nj]=A[nj][ni]=-d;
        nj++;
      }
      ni++;
    }
    f[S]=det(A);
  }
  // g 子集遍历
  rep(S,1,1<<n)rep(i,0,c[S])for(int T=S;T;T=(T-1)&S)if(T&S&-S and i-(c[T]-1)>=0)g[S][i]+=f[T]*g[S-T][i-(c[T]-1)];
  rep(k,1,n)printf("%d\n",(g[(1<<n)-1][k]*fac[k]/mint(m).pow(k)).val());
  return 0;
}

总结

Ex

1847年 基尔霍夫定律

基尔霍夫矩阵树定理: 无向图的生成树个数等于其Laplacian matrix的任意一个代数余子式的值。

Kirchhoff’s theorem

Kirchhoff’s theorem for directed multigraphs

该重学一遍线性代数了

参考

官方题解

abc 213 g

https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem

调和矩阵Laplacian matrix: https://en.wikipedia.org/wiki/Laplacian_matrix

https://en.wikipedia.org/wiki/Cauchy%E2%80%93Binet_formula

周冬: 生成树的计数及其应用(ppt+doc 两个版本)