Atcoder abc242

發表於 更新於 分類於 ， Disqus： 文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘
F(DP,容斥原理,排列组合)Ex(min-max容斥,概率论,贡献统计,DP)

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

F - Black and White Rooks

n行,m列

放b 个黑色,w个白色, 求任意黑 不与 白同行/同列 的 放法 mod 998244353

范围

n,m 50

b,w 2500

2s 1024

我的思路

emmm 如果能算出 放b个黑色后, 还有x位置可以放白色, 那么就是 binom(x,w)

然后当然不能枚举

所以考虑说 放了b个后, 剩余有x个位置可以放白色 有多少种方案

一个想法是插头dp, 做一个横切折线, dp[折线][已放黑色个数][折线以上的可放白色位置数] = 方案数

每个状态 O(1) 转移

但问题是 2^n n n^2, 显然没法搞

考虑交换行列, 把 黑色的平移交换到一块

则考虑黑色铺的占了 i0行j0列, 白色占了i1行j1列 的方案, 并且注意到行列看似有关系,但行与行交换不影响列的个数

最后乘上 binom(n,i0,i1) * binom(m,j0,j1)

问题是 直接行列的个数描述也可能多种

1
2
x0
0x

和

1
2
0x
x0

行列 都是(1,1)

dp[i][mask][j] = 前i行用了j个, 列占用情况是mask 的方案数, 依然状态就 n^3 2^n,

f(i,j,c) = 一共铺了(<=i,<=j) 的方案数 = binom(i * j, c)

有办法容斥出来吗?

题解

看起来主体思路方向一样

还是落到求 x个放来n行m列的 每行每列至少有一个的方案数

方案1 DP

f(n,m,x) = binom(n * m,x) - n行m列中 选i行,j列填满

f(n,m,x) = binom(nm,x) - sum binom(n,i)binom(m,j)f(i,j,x)

还真是这样减的

方案2 容斥

属性: 第?行放了其它行任意, 第?列放了其它列任意

属性的补集: 第?行没有放其它行任意, 第?列没有放其它列任意

属性的交 = 全集 - 属性的补的并

= sum (-1)^{i+j} * 1, 每个的贡献函数都是1

= sum (-1)^{i+j} binom(n,i) binom(m,j) binom((n-i)(m-j),x)

代码

https://atcoder.jp/contests/abc242/submissions/35002886

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
#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;}

mint fac[2510] = {1};
mint ifac[2510];
mint binom(int n,int m){
  if(m > n || m < 0) return 0;
  return fac[n] * ifac[m] * ifac[n-m];
}

mint binom(int n,int m0,int m1){
  if(m0+m1 > n || m0 < 0 || m1 < 0) return 0;
  return fac[n] * ifac[m0] * ifac[m1] * ifac[n-m0-m1];
}

mint memf[2][60][60];
bool visf[2][60][60];

mint f(int o,int n,int m,int x){
  auto & r = memf[o][n][m];
  if(visf[o][n][m]) return r;
  visf[o][n][m] = true;
  if(x > n*m) return r=0;
  r = binom(n*m, x);
  rep(i,1,n+1)rep(j,1,m+1)if(i!=n||j!=m)r-=binom(n,i)*binom(m,j)*f(o,i,j,x);
  return r;
}

int main(){
  rep(i,1,2500+1) fac[i] = fac[i-1]*i;
  ifac[2500] = fac[2500].inv();
  per(i,0,2500) ifac[i] = ifac[i+1]*(i+1);
  int n = read();
  int m = read();
  int w = read();
  int b = read();
  mint ans = 0;
  rep(i0,1,n+1)rep(j0,1,m+1)rep(i1,1,n+1-i0)rep(j1,1,m+1-j0) ans+=binom(n,i0,i1)*binom(m,j0,j1)*f(0,i0,j0,w)*f(1,i1,j1,b);
  
  printf("%d\n",ans.val());
  return 0;
}

Ex - Random Painting

n个白色格子

m个球 上面写了li,ri

重复直到所有格子变黑

每次 等概率随机选一个球, 把对应[li..ri]涂黑, 放回去

求全部涂黑的期望次数, mod 998244353

范围

n,m 400

3s

1024mb

我的思路

这个n影响不大,如果n很大你需要手动离散一下

也就是 给你m个线段,每次等概率选一个涂黑, 把整个区间涂黑和期望次数

想一些排序,dp感觉都没想法, n,m这么大 也不太能bitdp

题解

第一次遇到min-max容斥 是cf 1687 E, 也没有彻底学会,只是暴力推了公式,有个大概的印象, 这是第二次

那么就是集合的够建

s_i = 位置i被涂黑的次数(推导见下)

$E(\max(S)) = E(\sum_{T\subseteq S} (-1)^{|T|+1} \min(T)) = \sum_{T\subseteq S} (-1)^{|T|+1} E(\min(T))$

注意到 E(min(T)) 的取值范围是 $\frac{1}{1\cdots n}$

因此变成贡献统计

dp[i][j] = 前i个位置中,第i个必定选择, 与j个区间相交 的个数

dp[0][0] = -1

dp[i][j] += (-1) dp[k][j - 覆盖了i没有覆盖k的区间数], (k<i)

ans = sum dp[i][j] 1/p = sum dp[i][j] 1/(j/m) = sum dp[i][j] m / j

min-max 容斥

先上公式,$S$为集合

$\max(S) = \sum_{T\subseteq S} (-1)^{|T|+1} \min(T)$

对称的显然,相当于所有数字乘上负号 $min(S) = \sum_{T\subseteq S} (-1)^{|T|+1} max(T)$

用途: 当min容易求 而max难求时

证明

从思路角度上和 之前容斥的思路很像, 通过-1的幂次 反复乘做抵消

值两两不同, 对于第i小的值$a_i$是最小值的 所有S的子集T($a_i \in T$), 如果S中有比它大的,那么比它大的值通过选或不选 能让所在集合的T的元素为奇数个数和为偶数个数的一样多, 那么-1^集合大小 去作为倍数, 再相加, 就抵消了

而对于最大的来说, 它只出现一次

得证

min-max 容斥+期望

然后 注意到期望本质是 $\int p(x) dx$, 或者$\sum xp(x)$ , 是可以相加,有分配率的, 因此

$E(\max(S)) = E(\sum_{T\subseteq S} (-1)^{|T|+1} \min(T)) = \sum_{T\subseteq S} (-1)^{|T|+1} E(\min(T))$

使用

$n$个元素, 每次有概率$p_i$选其中一些元素$set_i$

$S$中$S_i$ 表示第$i$个元素首次被选的发生的次数, (不是期望次数, 而是每个具体的结果中的次数)

E(max(S)) = sum ( S中元素被选的次数的最大值 * 这种情况发生的概率) = sum ( S中所有被选 * 这种情况发生的概率) = S所有被选的期望次数

E(min(T)) = sum ( T中元素被选的次数的最小值 * 这种情况发生的概率) = sum ( T中有>=1个被选 * 这种情况发生的概率) = T中>=1个被选的期望次数

如何计算E(min(T))

考虑 min(T) = t 的概率, 那么就是 t-1次都没有选中T中任何一个, 在t次选中了

那么令单次 选中的区间和T重叠的概率为p(T) = 覆盖了T中任意一个点的线段数/总线段数

$E(min(T)) = \sum_{t=1}^{\infty} t p (1-p)^{t-1} = -p(\sum_{t=1}^{\infty} (1-p)^t)’ = -p ((1-p)\frac{1}{1-(1-p)})’ = -p(\frac{1}{p}-1)’ = \frac{1}{p}$

代码

https://atcoder.jp/contests/abc242/submissions/35019791

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}
mint f[410][410]; // f[i][j] = 前i个,第i个必选, 所选的下标被j个线段覆盖过 的 (方案数 * (-1)^(选点数+1)) 的和
int c[410][410]; // c[i][j] = 覆盖了下标i,但是没有覆盖下标j的区间, (i>j)
int main(){
  int n = read(); // 400
  int m = read(); // 400
  rep(k,0,m) {
    int l = read(); // 下标1-index, 方便直接表示个数 和 0个的表示
    int r = read();
    rep(i,l,r+1) rep(j,0,l) c[i][j]++;
  }
  f[0][0]=-1; // (-1)^(点数+1) = (-1)^(0+1) = -1;
  rep(i,1,n+1) rep(j,0,i) rep(k,0,m+1) if(k+c[i][j] <= m) f[i][k+c[i][j]]-=f[j][k]; // i选择,j到i之间都没有选,j是上一个选的位置, 增加覆盖i 而未覆盖j的线段数 c[i][j]
  mint ans = 0;
  rep(i,1,n+1) rep(k,1,m+1) ans+= f[i][k] * m/k; // E(max(S)) = (-1)^{点数+1} 总线段数/被覆盖数
  printf("%d\n",ans.val());
  return 0;
}

总结

F

dp 应该再多推一下能想到的

容斥还是不熟, 总是把属性以外的是任意 而不是不选 这一点想错, 另外因为通过容斥, 最后出来的每个元素 都是”需要的”, 所以不要再去判断是否”合法”,而直接是每个的贡献就是了, 感觉又熟悉了一点

Ex

感觉最近看了好几个这种 -1 幂次玩抵消的

算拉通证明了一下min-max容斥,以及在期望中的使用,

然后这个题, 这里的连续区间似乎并不必要, 可以看 洛谷 P3175 HAOI2015 的那个题目, 就是每次给一组点也是一样的

参考

官方题解

https://yexiaorain.github.io/Blog/cf/1687/

luogu command_block min-max 容斥

洛谷 P3175