Atcoder abc331

發表於 更新於 分類於 ， Disqus： 文章字數： 626 所需閱讀時間 ≈ 2 分鐘
G(min-max容斥，生成函数，NTT)

https://atcoder.jp/contests/abc331

G - Collect Them All

n 卡

数字 1~m

c[i]张卡 写着i

随机 抽取一个卡, 记录抽过的卡, 放回箱子

求 exp(次数) 直到每种数字至少被抽到一次, mod 998244353

m <= n <= 2e5

2s

1024mb

我的思路

这 看起来是 min-max 容斥吗？

对于一个具体的方案，有对应的集合$S=\lbrace t_1,t_2,\cdots,t_m \rbrace$ 表示每个元素首次发生的次数

那么$\max(S)$就是 完成的时刻

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

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

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

也就是 t-1次没有选中T内的任何一个,而第t次选中了

设选中的概率 为$\displaystyle p_T = \frac{\sum_{i\in T} c_i}{N}$

$E(\min(T)) = \sum_{t=1}^{\infty} tp(1-p)^{t-1}= -p(\sum_{t=1}^{\infty}(1-p)^t)’$, 把p看作一元变量

$=-p((1-p)\frac{1}{1-(1-p)})’$

$=-p((\frac{1}{p}-1)’$

$=\frac{1}{p}$

$\displaystyle \mathrm{ans}=\sum_{T\subset S} (-1)^{|T|+1} \frac{N}{\sum_{i\in T}c_i}$

所以如果能求得 所有$\lbrace 1,2,\cdots,m \rbrace$子集的$c_i$和 对应的$(-1)^{|T|+1}$ 就好了

因为$c_i$和是小于N的

注意到 $\displaystyle -(1-x^{sz_1})(1-x^{sz_2})\cdots(1-x^{sz_m})$的系数，就是要求的内容

代码

https://atcoder.jp/contests/abc331/submissions/50048769

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
#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
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++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)

ll read(){ll r;scanf("%lld",&r);return r;}
using poly=vector<mint>;
const int N=200000;
int c[N+10];
mint fac[N+10]={1};
mint ifac[N+10]={1};
mint inv[N+10]={1};
int main(){
  rep(i,1,N+1) fac[i]=fac[i-1]*i;
  ifac[N]=fac[N].inv();
  per(i,0,N) ifac[i]=ifac[i+1]*(i+1);
  rep(i,1,N+1) inv[i] = ifac[i]*fac[i-1];
  int n=read();
  int m=read();
  rep(i,1,m+1) c[i]=read();
  vector<poly> all;
  all.push_back({-1});
  rep(i,1,m+1) {
    poly gf(c[i]+1,0);
    gf[0]=1;
    gf[c[i]]=-1;
    all.push_back(gf);
  }
  while(all.size() > 1){
    rep(i,0,all.size()/2) all[i] = convolution(all[i],all[(all.size()+1)/2+i]);
    all.resize((all.size()+1)/2);
  }
  assert((int)all[0].size() == n+1);
  mint ans = 0;
  rep(i,1,n+1) ans += all[0][i]*inv[i];
  printf("%d\n",(ans*n).val());
  return 0;
}

总结

这是第3次遇到min-max 容斥了吧, 之前有atcoder abc242 和 codeforces 1687,不过这是第一次自己做出来，虽然编码不快，但是算自己能完整首次做出一个新算法,可喜可贺

橙题也正常