【300iq Contest 1 H】Hall‘s Theorem 题解

题目大意

  一个二分图，设左边的一个点集为 $S$，记它在右边的邻集为 $N(S)$，如果 $|S|>|N(S)|$，则称 $S$ 是 critical 的。
  给定 $n,k$，构造一幅左右各 $n$ 个点的二分图，使得 critical 的点集数量恰好为 $k$。

  $n < 20,\ 0 \le k < 2^n$
  1s

题解

  （虽然题解提到杨表但是并不能理解如何用杨表解释这个题 qaq
  不过杨表的结构却是很有启示性。

  先把 $k$ 换成非空非 critical 点集数 $2^n-1-k$。假设左边每个点 $i$ 都连向右边的一个前缀 $1,\cdots,a_i$，那么左边的每一个点集只取决于其 $a_i$ 最大的点。把左边的点按 $a_i$ 从小到大排序，那么一个点 $i$ 的贡献就是 $\sum_{j=0}^{a_i-1} \binom{i-1}{j-1}$。
  那么可以看成有一个 $n^2$ 的网格图，元素 $(i,j)$ 的价值是 $\binom{i-1}{j-1}$。现在每一行选一个前缀，每一行的长度要大于等于上一行，问是否存在一种方案使得价值和为 $k$。

  题解给的标准做法是 $O(\frac{n^32^n}{64})$ dp，设 $dp_{i,j}$ 表示目前到第 $i$ 行，这行选的前缀长度为 $j$，所能取到的价值和的 bitset。
  但是观察一波发现可以从下往上贪心。从最后一行开始，每行从左到右，能选则选，不能选则往上一行。
  不会证明，只能马后炮地归纳证明一下。归纳证明左上角为 $(1,1)$ 右下角为 $(n,m)$ 的子矩阵可以取到所有不超过矩阵元素和的价值和。$n=1$ 时显然满足。$n>1$ 时，要么最后一行取满了，那么剩余价值和一定不超过去掉最后一行的子矩阵的元素和；要么最后一行没取满，只取到 $(n,j)$，则剩余价值和不超过 $value_{n,j+1}=\binom{n-1}{j}$，而 $\sum_{i=0}^{n-2} \binom{i}{j-1}=\binom{n-1}{j}$，所以剩余价值和也不超过去掉最后一行的子矩阵的元素和。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

const int maxn=25;

int n,k;
vector<pair<int,int>> e;

int C[maxn][maxn];
void C_Pre(int n)
{
	fo(i,0,n)
	{
		C[i][0]=1;
		fo(j,1,i) C[i][j]=C[i-1][j-1]+C[i-1][j];
	}
}

int main()
{
	scanf("%d %d",&n,&k);
	k=(1<<n)-k-1;
	
	C_Pre(n);
	
	int cur=0;
	fd(i,n,1)
		fo(j,1,n)
			if (cur+C[i-1][j-1]>k) break; else
			{
				cur+=C[i-1][j-1];
				e.push_back(make_pair(i,j));
			}
	
	printf("%d\n",e.size());
	for(auto p:e) printf("%d %d\n",p.first,p.second);
}