Deltix Round, Summer 2021

發表於 更新於 分類於 ， Disqus： 文章字數： 2k 所需閱讀時間 ≈ 7 分鐘
F 图，互斥拆分，bitset枚举子集，概率论

F

https://codeforces.com/contest/1556/problem/F

比赛n个队伍$(n\leq 14)$

第i个队伍有个$a_i(1\leq a_i \leq 10^6)$

i队和j队打，分别的获胜概率为$\frac{a_i}{a_i+a_j}$ 和 $\frac{a_j}{a_i+a_j}$

任意两个队之间打且仅打一场

如果 i直接战胜j 或者 间接战胜 i 战胜 ? 战胜 ? 战胜 j ，都算战胜j, （也就意味着 i战胜了j，j也同时战胜了i）

如果一个队战胜了其它所有队，那么它是winnner

求winner个数的期望值($\mod 10^9+7$ 意义下)

题解

我的初步思路

抽象成数据结构

n个点，任意两点之间有且仅有一条有向边，有向边的方向通过上述概率决定，求能走到所有点的点的个数期望值

边数 最大 $\frac{14 \cdot 13}{2} = 91$

如果一点是winner，那么进入该点的都是winner

如果一系列点构成环，那么它们要么同时是 winnner，要么同时不是winnner

单winnner 存在一个点入度为0，其它点入度全大于0，剩余点的边无论怎么排，都是单winner

双winner 不可能， 因为 两点互相能到，任意两点之间直连是仅有一条的单向边，路径上必定有其它的点，那么其它的点也是winner，必定多余2个winner

三winner 同双winner的互相可达原理，和可达路径上的点也是winner的原理，三个winner 构成环，且3个winner以外的边和它们连接全是出度，没有入度，同样剩余点的边无论怎么排都是3winner

同理

m个winner，意味着，这m个两两可达，且对m个以外的边全是出度

期望来了，

每次选m个点，让它们两两可达的概率和所有其它边是出度的概率 * m 再求和

其它边都是出度的概率好求

n=14 枚举点的话，也只有 $2^{14} = 16384$

那么问题变成了，给定m个点，求其内部两两可达的概率

和上面类似的，如果 A -> B, 那么如果B能到 其它所有，无论A的剩余边怎么连都是A也能到其它所有，且显然 B -> A还有一条非直连的简单路径

但这只是保证了A,B两个点，并不是两两可达

剩余

首先官方题解的拆分是一样的， 也是聚集到如何计算 P(winnners)

这里容斥 + 切

也就是 在winnners中选取集合subs, 集合中两两可达

subs 中所有向 $ winnners - subs$ 都是胜利的方案，这样保证了这些都是两两可达的。 这里需要证明能覆盖所有非两两可达，因为如果不是所有两两可达，那么对其中局部两两可达的进行缩点，缩点后，整个拓扑有序的，所以能找到一条切割方案， 让一侧战胜另一侧,源点两两可达（因为所有点之间都有有向路径，不可能存在多余一个的0入度的点，所以至多一个无入度的点，那么这个点缩点前就是subs）,所以上面的是充要的

下面证明，不同subs选取的互斥性

对于同一个winnners， subs0 和 subs1 的点选取不同，则至少有一个点，在且仅在其中一个集合中，那么subs0 和 subs1 中的能到subs的点集已经不同了，那么subs0和subs1 不会重复

所以 这里说是容斥，但是实际上，是选取的互斥，又全覆盖的划分

P(集合) = 集合中两两可达的概率

G(集合A,集合B) = 集合A 任何人，战胜 集合B 所有人的概率 （切的概率）

F(集合) = 仅集合内全是winners（集合外全不是winnners）的概率

ALL 所有人

$|集合| = 集合大小$

$答案 = sum( F(winners) * |winnners|)$ 概率乘值，期望公式

$F(winners) = P(winnners) \cdot G(winnners, ALL - winnners)$ 上面的结论，winnners 打败所有非winners

$P(winners) = 1 - sum ( P(sub) \cdot G(sub, winnners - sub) )$ 上面的互斥拆分

G 没啥好说，就是切上

$G(X,Y) = \prod_{\forall x\in X, \forall y \in Y} \frac{a_x}{a_x+a_y}$

公式递推起来似乎可以做了

然而，状态看起来有 $(2^n)^2$ 个，还不包括状态等，超界了

$G(X,Y) = \prod_{\forall x \in X} (\prod_{\forall y \in Y \frac{a_x}{ax+a_y}})$

于是对于每个x,我们可以 $O(2^n)$ 计算，所有的x对于不同的Y,可以 $O(n 2^n)$计算出

那么对于一个给定$G$可以 O(n) 计算出

没太懂，这里$G_{sidefrom,sideto}$ 是怎么回事

代码

这里我想的有问题, 没有正确估计到复杂度，

虽然是枚举 i去算集合,sub 是i的子集，但是 复杂度并不是$O(2^n \cdot 2^n \cdot n)$ , 分别是 i,sub,和G(sub,i-sub);

下面次数也是大概，没有那么准确，比如空和全没有排除

sub 的个数 $\sum_{i=1}^n C_i^n \cdot 2^i$

G内部计算次数 $\sum_{i=1}^n C_i^n \cdot \sum_{j=1}^{i} C_j^i \cdot j = 3^{n-1} \cdot n$, n = 14 时表达式的值为 $3^{13} \cdot 14 = 22320522$

证明见wolframalpha 或下方

当然通过代码cnt++也可以统计

1
2
3
4
n = 14
i = 16383
cross = 4766585
cross ret = 22320522  
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
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
// 末尾零的个数
#define ctz __builtin_ctz
#define popc __builtin_popcount
const int N = 16, N2 = 16400; // 2**14=16384

int n;
int a[N];
ll G[N][N]; // G[i][j] = a[i]/(a[i]+a[j])
ll cr[N][N2]; // [点][bit mask state]
ll prob[N2];

ll PowerMOD(ll a, int n, ll c = 1) {
  for (; n; n >>= 1, a = a * a % MOD)
    if (n & 1) c = c * a % MOD;
  return c;
}

// 点集A战胜点集B,O(n)
int cross(int A, int B) {
  ll ret = 1;
  // 每次去掉A的最后一个1
  for (; A; A &= A - 1) {
    ret = ret * cr[ctz(A)][B] % MOD;
  }
  return ret;
}

int main() {
  ll ans = 0;
  cin >> n;
  int ALL = ~(-1 << n);
  rep(i,0,n){
    scanf("%d",a+i);
  }

  // G[i][j] = a[i]/(a[i]+a[j])
  // 没有特殊处理 i == j
  rep(i,0,n){
    rep(j,0,n){
      G[i][j] = PowerMOD(a[i] + a[j], MOD - 2, a[i]);
    }
  }
  // O(n * 2^n) , 每个点i，战胜点集合j(bit mask)
  // 没有特殊处理 i \in j 之后计算不会使用即可
  rep(i,0,n){
    cr[i][0] = 1;
    rep(j,1,ALL+1){
      cr[i][j] = cr[i][j & (j - 1)] * G[i][ctz(j)] % MOD;
    }
  }
  // ans = sum{ |popc(i)| * prob[i]         * cross(i,j) }
  //             winner数   winner内部互连    winnner战胜非winner
  //
  // prob[i] = 1 - sum { prob(sub) * cross(sub, i - sub)  }

  // 次数
  // n = 14
  // i = 16383
  // cross = 4766585
  // cross ret = 22320522
  rep(i,1,ALL+1){
    prob[i] = 1;
    // 这里对 i 的 子集全枚举
    for (int j = i & (i - 1); j; j = (j - 1) & i){
      (prob[i] -= prob[j] * cross(j, i - j)) %= MOD;
    }
    (ans += prob[i] * cross(i, ALL - i) % MOD * popc(i)) %= MOD;
  }
  printf("%lld\n", (ans+MOD) % MOD );
  return 0;
}

附

$\sum_{i=1}^n C_i^n \cdot \sum_{j=1}^{i} C_j^i \cdot j $

= $\sum_{i=1}^n \frac{n!}{i!(n-i)!} \cdot \sum_{j=1}^{i} \frac{i!}{j!(i-j)!} \cdot j $

= $\sum_{i=1}^n \frac{n!}{i!(n-i)!} \cdot \sum_{j=1}^{i} \frac{(i-1)!}{(j-1)!(i-j)!} \cdot i $

= $n \cdot \sum_{i=1}^n \frac{(n-1)!}{(i-1)!(n-i)!} \cdot \sum_{j=1}^{i} \frac{(i-1)!}{(j-1)!(i-j)!} $

= $n \cdot \sum_{i=0}^{n-1} C_{i}^{n-1} \cdot \sum_{j=0}^{i-1} C_{j}^{i-1} $

= $n \cdot \sum_{i=0}^{n-1} C_{i}^{n-1} \cdot (1+1)^{i-1}$

= $n \cdot \sum_{i=0}^{n-1} C_{i}^{n-1} \cdot 2^{i-1}$

= $n \cdot (1+2)^{n-1}$

= $n \cdot 3^{n-1}$

总结

  1. 看到14，12，20这类数，能一下向bit想，是习惯
  2. 互斥拆分还需要多练习增加经验
  3. 高效内置库，末尾0个数，所有1个数#define ctz __builtin_ctz,#define popc __builtin_popcount
  4. 乘 除 模 同优先级能省掉部分括号 加快代码编写
  5. bit 子集枚举 for (int j = i & (i - 1); j; j = (j - 1) & i){
  6. clang overflow 提示 开关 https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html

ref

官方题解

yhx-12243 code