题目大意：给你n个男的和n个女的，有一些男女之间有连边，要你选出最多的人，使得每个男的都和每个女的有连边，如果存在多种情况，选男的人数最多的那种，求男的和女的的个数，再给你一个k，要从选出的人当中选出k个边，每个人都至少被一条边覆盖过，求方案数mod 19921228 n<=50 k<=2500
这道题首先可以分成两个部分，先求男的女的有多少个，再求方案数。
第一个的话，由于要选出的男女必须有连边，那我们就建原图的补图，那么有连边的就不能同时选了。那么这就变成二分图的最大独立集了，可以转化为最小覆盖，我们可以用最小割来做，先在还要求男的数量尽量多，那么就只要把S连向男的的边权定为n+1，女的边权定为n，那么选出来的就既是最小覆盖又是男的最少的了，为什么是男的最少呢，因为这是求最小覆盖，男的最少，那在最大独立中男的就最多了。这样，第一问就解决了
第二个的话，可以用容斥，就是
（图片是贴别人的。。。）
那么这样就可以Ac了，但是打开rank一看发现400+ms，但是rank one只有80ms，于是深度膜拜了rank one的代码，终于研究了出来
在预处理C的时候，因为i*j是n^2级别的，所以是O(n^4)的，所以就慢了，我们惊讶的发现当C的下方很大时，上方都是一个固定的数，于是我们就想到可以用C(i,k)=C(i-1,k)*i/(i-k)来推，但是这里有除法，mod的数又不是质数，所以非常蛋疼，我们发现19921228 =2*2*1873*2659的，只要先把其中的2与1873都除去，且被除的数都小于2659，那么剩下的肯定就与19921228 互质了，于是我们就可以愉快的求逆元了，直接用欧拉定理就OK了，这样就快的飞起了
慢慢的
#include<cmath>
#include<cstdio>
#include<cassert>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=55,maxp=maxn*2,maxe=5211,inf=~0u>>1,mod=19921228;
int n,k,m; bool edge[maxn][maxn];
void init(){
int a,b; scanf("%d%d%d",&n,&k,&m); memset(edge,0,sizeof(edge));
for (int i=1;i<=m;++i) scanf("%d%d",&a,&b),edge[a][b]=1;
}
int tot=1,v[maxe],son[maxe],pre[maxe],now[maxp];
inline void add(int a,int b,int c){pre[++tot]=now[a]; now[a]=tot; son[tot]=b; v[tot]=c;}
inline void cc(int a,int b,int c){add(a,b,c); add(b,a,0);}
int dep[maxp],q[maxp];
int st,ed;
bool bfs(){
memset(dep,0,sizeof(dep));
q[1]=st; dep[st]=1; int w=1;
for (int i=1;i<=w;++i){
for (int p=now[q[i]];p;p=pre[p]) if (v[p] && !dep[son[p]])
dep[son[p]]=dep[q[i]]+1,q[++w]=son[p];
}
return dep[ed]?1:0;
}
int find(int x,int f){
if (x==ed) return f; int ans=0;
for (int p=now[x];p;p=pre[p]) if (v[p] && dep[son[p]]>dep[x]){
int k=find(son[p],min(f,v[p]));
v[p]-=k; v[p^1]+=k; ans+=k; f-=k;
if (!f) return ans;
}
dep[x]=0; return ans;
}
int zg(){
int ans=0; while (bfs()) ans+=find(st,inf); return ans;
}
int c[maxn*maxn][maxn*maxn];
void work(){
st=2*n+1,ed=st+1; tot=1;
for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) if (!edge[i][j]) cc(i,n+j,inf);
for (int i=1;i<=n;++i) cc(st,i,100),cc(i+n,ed,99);
int tmp=zg(),lp=tmp-tmp/99*99,rp=tmp/99-lp; lp=n-lp; rp=n-rp;
long long ans=0; int xx=lp*rp; for (int i=1;i<=xx;++i) c[i][0]=c[i][i]=1;
for (int i=1;i<=xx;++i) for (int j=1;j<i;++j) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
for (int i=1;i<=lp;++i) for (int j=1;j<=rp;++j){
int x=1LL*c[lp][i]*c[rp][j]%mod*c[i*j][k]%mod;
if (((i+j)^(lp+rp))&1) ans-=x; else ans+=x;
}
printf("%d %d\n%d\n",lp,rp,(ans%mod+mod)%mod);
}
int main(){
init();
work();
return 0;
}
快快的
#include<cmath>
#include<cstdio>
#include<cassert>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=55,maxp=maxn*2,maxe=5211,inf=~0u>>1,mod=19921228;
int n,k,m; bool edge[maxn][maxn];
void init(){
int a,b; scanf("%d%d%d",&n,&k,&m); memset(edge,0,sizeof(edge));
for (int i=1;i<=m;++i) scanf("%d%d",&a,&b),edge[a][b]=1;
}
int tot=1,v[maxe],son[maxe],pre[maxe],now[maxp];
inline void add(int a,int b,int c){pre[++tot]=now[a]; now[a]=tot; son[tot]=b; v[tot]=c;}
inline void cc(int a,int b,int c){add(a,b,c); add(b,a,0);}
int dep[maxp],q[maxp];
int st,ed;
bool bfs(){
memset(dep,0,sizeof(dep));
q[1]=st; dep[st]=1; int w=1;
for (int i=1;i<=w;++i){
for (int p=now[q[i]];p;p=pre[p]) if (v[p] && !dep[son[p]])
dep[son[p]]=dep[q[i]]+1,q[++w]=son[p];
}
return dep[ed]?1:0;
}
int find(int x,int f){
if (x==ed) return f; int ans=0;
for (int p=now[x];p;p=pre[p]) if (v[p] && dep[son[p]]>dep[x]){
int k=find(son[p],min(f,v[p]));
v[p]-=k; v[p^1]+=k; ans+=k; f-=k;
if (!f) return ans;
}
dep[x]=0; return ans;
}
int zg(){
int ans=0; while (bfs()) ans+=find(st,inf); return ans;
}
int lp,rp;
int c[maxn][maxn];
void getc(){
int xx=max(lp,rp); for (int i=1;i<=xx;++i) c[i][0]=c[i][i]=1;
for (int i=1;i<=xx;++i) for (int j=1;j<i;++j) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
inline int power(int x,int t){
int tmp=x,ans=1;
while (t){
if (t&1) ans=1LL*ans*tmp%mod;
t>>=1; tmp=1LL*tmp*tmp%mod;
}
return ans;
}
int C[maxn*maxn];
void getC(){
int xx=lp*rp,p[2],s[2],last=1,ny=9951551; // 9951551 is fai(mod)-1
p[0]=2; p[1]=1873; s[0]=s[1]=0; C[k]=1;
for (int i=k+1;i<=xx;++i){
int a=i,b=i-k; // C(i,k)=C(i-1,k)*i/(i-k)
for (int t=0;t<2;++t) while (a%p[t]==0) ++s[t],a/=p[t];
for (int t=0;t<2;++t) while (b%p[t]==0) --s[t],b/=p[t];
last=1LL*last*a%mod; last=1LL*last*power(b,ny)%mod;
C[i]=1LL*last*power(p[0],s[0])%mod*power(p[1],s[1])%mod;
}
}
void work(){
st=2*n+1,ed=st+1; tot=1;
for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) if (!edge[i][j]) cc(i,n+j,inf);
for (int i=1;i<=n;++i) cc(st,i,100),cc(i+n,ed,99);
int tmp=zg(); lp=tmp-tmp/99*99; rp=tmp/99-lp; lp=n-lp; rp=n-rp;
long long ans=0; getc(); getC();
for (int i=1;i<=lp;++i) for (int j=1;j<=rp;++j){
int x=1LL*c[lp][i]*c[rp][j]%mod*C[i*j]%mod;
if (((i+j)^(lp+rp))&1) ans-=x; else ans+=x;
}
printf("%d %d\n%d\n",lp,rp,(ans%mod+mod)%mod);
}
int main(){
init();
work();
return 0;
}