Atcoder abc215

G - Colorful Candies 2

N 个 有色糖果,第i个颜色c[i]

从中选K个有 binom(N,K)种方案

等概率选一种方案

价值=所选的颜色的不同的数量

对于每个 k= 1…N 求期望价值

mod 998244353

限制

N 5e4

c[i] [1,1e9]

4s

1024mb

我的思路

首先只关心不同值,显然c[i]可以离散化到[1..N]

答案 = sum{价值} / binom(N,K)

不同颜色互不影响

所以 选了j种颜色, 一共k个, 如果能算方案出来 f(j), 那么答案 = sum j * f(j)

指定的 c[…] 中选的话

似乎可以卷积

去表示每个颜色 选t个的方案数, 然后卷积意义是前 j 种颜色(可能有的不选) 选k个的方案数

好像无法获得选了几个颜色

题解

反过来, 也就是每个颜色出现一次的概率 的贡献和

P(出现一次) = 1-P(一次都不出现)

binom(n-x,k) / binom(n,k) , 也就是x 是这个颜色的个数

其中 n-x < k 的话, 必定出现p = 1

(binom(n,k) - binom(n-x,k))/binom(n,k) , 也就是x 是这个颜色的个数

可以减少计算

注意到 可以统计个数为x的有多少个, 这样最多 $\sqrt(N)$个统计

因此对于k来讲,是$O(\sqrt{N})$的

总的便是$O(N^{\frac{3}{2}})$

代码

https://atcoder.jp/contests/abc215/submissions/33712411

#include <bits/stdc++.h>
#include <atcoder/all>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
const int MOD = 998244353;
#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;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int c[50010];
mint fac[50010] = {1};
mint invv[50010] = {0,1};
mint invfac[50010] = {1};

mint binom(int n,int m){
  if(m > n) return 0;
  return fac[n] * invfac[m] * invfac[n-m];
}

int main(){
  int n = read();
  rep(i,0,n) c[i] = read();

  rep(i,1,n+1) fac[i] = fac[i-1] * i;
  invv[1] = 1;
  rep(i,2,n+1) invv[i] = (MOD - MOD/i) * invv[MOD%i];
  rep(i,1,n+1) invfac[i] = invfac[i-1] * invv[i];

  sort(c,c+n);
  vector<int> sz = {1};
  rep(i,1,n){
    if(c[i] != c[i-1]){
      sz.push_back(1);
    }else{
      sz.back()++;
    }
  }
  sort(sz.begin(),sz.end());
  vector<pair<int,int>> sc; // size count
  int cnt = 0;
  rep(i,0,sz.size()){
    cnt++;
    if(i+1 == (int)sz.size() || sz[i] != sz[i+1]){
      sc.push_back({sz[i],cnt});
      cnt = 0;
    }
  }

  rep(k,1,n+1){
    mint bnk = binom(n,k);
    mint ans = bnk * sz.size() ;
    for(auto [s,t]:sc) {
      if(n-s < k) break; // n-s < k 的话, 必定出现p = 1
      ans -= binom(n-s,k) * t; // * 次数
    }
    ans /= bnk;
    printf("%d\n",ans.val());
  }
  return 0;
}

G - Cabbage Master

N种菜,每种 A[i] 个

M个需求, 每个需求B[i] 个, 但是限制c[i][j] = 0/1 表示第i个需求 是否允许得到 第j种菜

如果 能满足所有需求则 成功

现在要尽量少的删除一些菜的个数, 让它无法成功

并且求, 删除同样数量的方案数 mod 998244353

限制

n 20

m 1e4

a[i] 1e5

b[i] 1e5

3s

1024mb

我的思路

一眼感觉网络流, 但是看着这n这么少

又觉得说 会不会是 maskdp

2^20 = 1048576, 大概1e6

---

网络流思路

就是 S -> Ini 流量 A[i]

Ini -> Outj 流量无限 如果c[i][j] == 1

Outj -> T 流量B[i]

那么目标是让最小割(最大流) <= sum B[i] 即可

题解

二分图

左侧N个颜色, 右侧M个需求

注意到 这里成功对应的是 匹配 = sum 右侧

所以是枚举右侧的的点集,看对应左侧的点集是否大于等于右侧

左侧L, 右侧R

要能完美匹配 $\forall S \subset R $

左侧对应集合并的和 $\ge S$对应需求的和

即 min (左侧对应集合并的和 - S对应需求的和) >= 0

---

n=20, 考虑枚举左侧的并,来找右侧的max

但似乎通过枚举子集可能有m 2^n 复杂度

但实际上我们要的是

min {f(L0) - g(L0)} >= 0, 其中f 算的集合里左侧的和, g 算的映射到左侧包含于集合的右侧的值的和 (既然B[i] 都是正的,那就是所有的加起来让g达到最大

g中计算 子集和可以sosdp 高维前缀和

那么删除数量X = min( f(L0) - g(L0)) + 1

---

然后问题变成如何计算方案数

ans = 0 , 不操作1种

对于ans > 0

设 左侧移除的X的值 来自的点集合恰好为S

当存在 S1 满足 S 是 S1 的子集, 且 f(L0) - g(S1) + 1 == X, 这时 S移除X的方案数h(S) 会有贡献

binom(S的个数,X) = sum h(T), T 是S的子集

这就是 子集反演问题

$h(S) = \sum (-1)^{|S|-|T|} binom(T的个数,X)$, T是S的子集

又是求子集的函数和, 那么这里把和原集合有关的移动一下

$(-1)^{|S|} {h(S)} = \sum (-1)^{|T|} \binom{f(T)}{X}$, T是S的子集

同样FWT, SOSDP可以处理

子集反演

$g(S) = \sum f(T)$, T是S的子集合

$f(S) = \sum (-1)^{|S| - |T|} g(T)$ , T是S的子集合

代码

https://atcoder.jp/contests/abc215/submissions/33719233

#include <bits/stdc++.h>
#include <atcoder/all>
using mint = atcoder::modint998244353;
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;} // read

const ll INF = 0x3f3f3f3f; // > 1e9
const int N = 20;
const int MASK = ( 1 << N ) ;
const int M = N * 100000;

mint fac[M+10] = {1}; // 阶乘
mint ifac[M+10] ={1}; // 阶乘的逆向

int f[MASK+10]; // f[1 << i] = A[i], f[mask] = sum A
int g[MASK+10]; // g[左侧mask] = sum B , 通过sosdp 变成子集和
mint h[MASK+10]; // h(S=bitmask) S中移除 X 个的方案数,(每个恰好一个)
int cnt[MASK+10]; // mask 中1的个数
int cont[MASK+10]; // cont[mask] = 多少个父集合 是满足 最小代价为X的 在mask中移除让Hall定理触发不满足

int B[M+10]; // 读入
int adj[M+10]; // adj[右侧] = 左侧的bitmask

mint binom( int n, int m ) { return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m]; }

int main() {
  rep(i,1,M+1) fac[i] = fac[i - 1]*i;
  ifac[M] = fac[M].inv();
  per(i,0,M) ifac[i] = ifac[i + 1]*(i + 1);
  int n = read();
  int m = read();
  rep(i,0,n)f[1 << i]=read();//f[1 << i]=A[i]
  rep(j,0,m)B[j]=read();
  rep(i,0,n)rep(j,0,m) if(read())adj[j]|=1 << i; // 转换成mask
  rep(j,0,m)g[adj[j]] += B[j]; // g[对应左侧mask] += B[j]
  rep(mask,1,1 << n) cnt[mask] = cnt[mask >> 1] + ( mask & 1 ); // 计算1个数
  rep(mask,1,1 << n) f[mask] = f[mask&(-mask)] + f[mask&(mask-1)]; // 去掉最后一个1 和最后一个1的mask之和
  rep(pwr,0,n) rep(mask,1,1 << n) if(mask & (1 << pwr)) g[mask] += g[mask ^ (1 << pwr)]; // sosdp 高维前缀和
  rep(mask,0,1 << n) if(!g[mask]) g[mask] = -INF; // 右侧没有集合对应左侧集合是mask的子集合
  int X = INF; // 答案第一部分 删除个数
  rep(mask,1,1 << n) X = min(X,f[mask]-g[mask]+1 ); // Hall定理, min(左子集值和 - 右侧来源子集和)
  if(max(X,0) == 0) { // 本来就不合法
    printf( "0 1\n" );
    return 0;
  }
  // h'(S) = (-1)^|S| h(S) = sum (-1)^|T| binom(f[t], X) SOSDP
  rep(mask,1,1 << n) h[mask] = binom(f[mask], X) * (cnt[mask] & 1 ? -1 : 1);
  rep(pwr,0,n) rep(mask,0,1 << n) if(mask & (1 << pwr)) h[mask] += h[mask ^ (1 << pwr)];
  rep(mask,0,1 << n) h[mask] = h[mask] * ((cnt[mask] & 1)?-1:1);

  // SOSDP 父集合反演(本质上还是 子集反演, 你只是把每个mask 看成mask的取反即可, 最外层是pwr顺序, mask每次之间没有链式依赖,都是两两依赖, 所以mask不需要换顺序
  rep(mask,1,1 << n) if( f[mask] - g[mask] + 1 == X ) cont[mask] = 1;
  rep(pwr,0,n) rep(mask,0,1 << n) if(mask & (1 << pwr)) cont[mask ^ (1 << pwr)] += cont[mask]; // 统计父集合可行的次数

  mint ans = 0;
  rep(mask,0,1 << n) if(cont[mask]) ans += h[mask];
  printf("%d %d\n",X, ans.val());
  return 0;
}

总结

G

其实还算基础知识点, 如何批量算模拟元,批量阶乘和阶乘模逆元,如何基于它们快速bionom

然后就是概率统计变形状和相同次数统计变成$\sqrt{N}$

评分 2267 也差不多

H

二分图,霍尔(Hall)定理

二分图一定程度上, 就不在意初始设计的方向了, 因为是匹配, 内部是没有关系的

霍尔定理对于这种大于1流量的也适用(因为从本质上看 左/右侧最多k个, 无非是k个点, 有无穷大边, 无非是这些拆开后的左右侧按照原来的关系两两有边, 而这个思路是不是特殊题型还能反过来思考)

这种”任意”的条件，可以考虑是在哪个部分将它破坏的

还涉及到 子集反演(以及用子集反演完成父集合反演)

参考

官方题解

hall’s theorem