Atcoder abc242

發表於 更新於 分類於 ， Disqus： 文章字數： 1.9k 所需閱讀時間 ≈ 6 分鐘
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 容斥

  • 这部分,我把相关整理到algo的min_max里了, 结论是: $S$为集合
  • $\max(S) = \sum_{T\subseteq S} (-1)^{|T|+1} \min(T)$

令 $s_i = 位置i首次被涂黑经过的 时间(次数), s_i\in S$

那么 $\text{ans}=E(\max(S))$

根据min-max容斥和期望的线性性质 $E(\max(S)) = E(\sum_{T\subseteq S} (-1)^{|T|+1} \min(T)) = \sum_{T\subseteq S} (-1)^{|T|+1} E(\min(T))$

注意到 选取的$T$的集合, 每次被选中的概率是$x/m$,其中x表示有x个子区间有覆盖$T$的某个元素

  • 那么$E(\min(T))=m/x$
  • 因为 二项分布的性质,单次选中是$p$,那么$E(X)=\sum_{i=1}^{\infty} ip(1-p)^{i-1}=-\sum p\frac{d}{dp}((1-p)^i)=-p \frac{d}{dp}((1-p)\frac{1}{1-(1-p)})=-p\frac{d}{dp}(\frac{1}{p}-1)=-p (-\frac{1}{p^2})=\frac{1}{p}$

x的范围$[1,m]$,因此 分类讨论x, 变成贡献统计,注意 -1的加权

令 $dp[i][j]=\sum_{i\in T, f(T)=j, T\subset \lbrace 1,\cdots,i\rbrace}(-1)^{|T-1|}$

$\text{ans}=\sum_{i=1}^n\sum_{j=1}^m dp(i,j)\frac{m}{j}$

  • 解读$dp[i][j]$:前i个位置中,第i个必定选择, 与j个题目的区间相交 的个数(也就是分类讨论的x)
  • 前i个位置和第i个必须选择，实际上就是在分类 讨论T的最大的元素
  • 而后面 与j个相交，是在按照$\min$讨论来分类计算贡献系数
  • 所以综上$\text{ans}=\sum 分类T的最后一个元素\sum 分类E(\min(T))$

$dp[0][0] = -1$

转移:

  • 考虑T中的上一个元素是k
    • $dp[i][j] += (-1) dp[k][j - 覆盖了i没有覆盖k的区间数], (k<i)$

代码

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