容斥小结

本篇小结大部分都是广义容斥原理，你可以看看这篇容斥原理小结,shadow;

bzoj3622
  • 考虑糖果比药片大的对数比药片比糖果大的对数不太好考虑，我们先只考虑糖果比药片多的对数
  • 显然先排序，对每个糖果处理一个(num)表示有(num)个药片它小，设(dp[i][j])表示考虑前i个，有j对符合条件，转移方程$$dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*max(0,num[i]-j+1)$$,第一项代表不选第i个，第二项代表选，前面有(max(0,num[i]-j+1))个可以与他配对
  • 然后令(ans[i]=dp[n][i]*(n-i)!),没有配对的就直接阶乘乱放
  • 显然会算重，直接二项式定理容斥就行了
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i)
#define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i)
const int N=2000+5;
bool cmax(sign &a,sign b){return (a<b)?a=b,1:0;}
bool cmin(sign &a,sign b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
  T ans=0,f=1;
  char ch=getchar();
  while(!isdigit(ch)&&ch!='-')ch=getchar();
  if(ch=='-')f=-1,ch=getchar();
  while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
  return ans*f;
}
template<typename T>void write(T x,char y)
{
  if(x==0)
  {
      putchar('0');putchar(y);
      return;
  }
  if(x<0)
  {
      putchar('-');
      x=-x;
  }
  static char wr[20];
  int top=0;
  for(;x;x/=10)wr[++top]=x%10+'0';
  while(top)putchar(wr[top--]);
  putchar(y);
}
void file()
{
  #ifndef ONLINE_JUDGE
      freopen("3622.in","r",stdin);
      freopen("3622.out","w",stdout);
  #endif
}
const int mo=1e9+9;
int n,k;
int a[N],b[N];
void input()
{
	n=read<int>(),k=read<int>();
	k=(n+k)>>1;
	For(i,1,n)a[i]=read<int>();
	For(i,1,n)b[i]=read<int>();
}
int num[N],dp[N][N],ans[N];
void add(int &a,int b)
{
	a+=b;if(a>=mo)a-=mo;
}
int C[N][N],mc[N];
void init(int maxn)
{
	For(i,0,maxn)C[i][0]=C[i][i]=1;
	For(i,2,maxn)For(j,1,i-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	mc[0]=1;For(i,1,maxn)mc[i]=1ll*mc[i-1]*i%mo;
}
void work()
{
	int pos=0;
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	For(i,1,n)
	{
		while(pos<n&&b[pos+1]<a[i])++pos;
		num[i]=pos;
		
	}
	dp[0][0]=1;
	For(i,1,n)For(j,0,i)
	{
		dp[i][j]=dp[i-1][j];
		if(j)add(dp[i][j],1ll*dp[i-1][j-1]*max(num[i]-j+1,0)%mo);
	}
	Fordown(i,n,k)
	{
		ans[i]=1ll*dp[n][i]*mc[n-i]%mo;
		For(j,i+1,n)add(ans[i],mo-1ll*ans[j]*C[j][i]%mo);
	}
	write(ans[k],'
');
}
int main()
{
	file();
	input();
	init(max(n,k));
	work();
	return 0;
}
bzoj4361
  • 先设(dp[i][j])表示到第i位，最长不降子序列长为j的方案数，本来是(n^2)的，用(BIT)优化一下
  • (f[i])表示最长非降子序列长为j的方案之和，(f[i]=sum_{j=i}^{n}dp[j][i]*(j-i)!),删去的元素顺序随意
  • 算重，因为有些数列删到(i+1)时就已经满足要求，但我们还是把他删到了(i)，所以容斥为(ans=sum_{i=n}^{1}f[i]*(n-i)!-f[i+1]*(n-i-1)!*(i+1))，就是枚举是(i+1)的方案中删掉了哪一个数而非法的
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i)
#define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i)
const int N=2e3+5;
bool cmax(sign &a,sign b){return (a<b)?a=b,1:0;}
bool cmin(sign &a,sign b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
  T ans=0,f=1;
  char ch=getchar();
  while(!isdigit(ch)&&ch!='-')ch=getchar();
  if(ch=='-')f=-1,ch=getchar();
  while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
  return ans*f;
}
template<typename T>void write(T x,char y)
{
  if(x==0)
  {
      putchar('0');putchar(y);
      return;
  }
  if(x<0)
  {
      putchar('-');
      x=-x;
  }
  static char wr[20];
  int top=0;
  for(;x;x/=10)wr[++top]=x%10+'0';
  while(top)putchar(wr[top--]);
  putchar(y);
}
void file()
{
  #ifndef ONLINE_JUDGE
      freopen("4361.in","r",stdin);
      freopen("4361.out","w",stdout);
  #endif
}
int n,a[N];
void input()
{
	n=read<int>();
	For(i,1,n)a[i]=read<int>();
}
const int mo=1e9+7;
int dp[N][N];
void add(int &x,int y)
{
	x+=y;if(x>=mo)x-=mo;
}
struct BIT
{
	int sum[N];
	void update(int x,int v)
	{
		for(;x<=n;x+=x&-x)add(sum[x],v);
	}
	int cal(int x)
	{
		int res=0;
		for(;x;x-=x&-x)add(res,sum[x]);
		return res;
	}
}s[N];
int mc[N],ans;
int f[N],q[N],top;
void init()
{
	For(i,1,n)q[i]=a[i];
	sort(q+1,q+n+1);
	top=unique(q+1,q+n+1)-q-1;
	For(i,1,n)a[i]=lower_bound(q+1,q+top+1,a[i])-q;
	mc[0]=1;For(i,1,n)mc[i]=1ll*mc[i-1]*i%mo;
}
void work()
{
	For(i,1,n)
	{
		Fordown(j,n,2)
		{
			add(dp[i][j],s[j-1].cal(a[i]));
			s[j].update(a[i],dp[i][j]);
			add(f[j],dp[i][j]);
		}
		dp[i][1]=1;s[1].update(a[i],dp[i][1]);
		f[1]++;
	}
	//For(i,1,n)For(j,1,n)write(dp[i][j],j==n?'
':' ');
	Fordown(i,n,1)
	{
		add(ans,1ll*f[i]*mc[n-i]%mo);
		add(ans,mo-1ll*f[i+1]*mc[n-i-1]%mo*(i+1)%mo);
	}
	write(ans,'
');
}
int main()
{
	file();
	input();
	init();
	work();
	return 0;
}
bzoj4710
  • 一开始疯狂考虑同一种特产算重的情况，思路完全错误了
  • 因为所有人都要有，所以我们枚举有几个人分到了特产，设(f[i])表示有i个人分到了特产，那么(f[i]=prod_{j=1}^{m}C[a[j]+i-1][i-1])，然后直接二项式容斥就行了
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i)
#define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i)
const int N=1000+5;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
  T ans=0,f=1;
  char ch=getchar();
  while(!isdigit(ch)&&ch!='-')ch=getchar();
  if(ch=='-')f=-1,ch=getchar();
  while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
  return ans*f;
}
template<typename T>void write(T x,char y)
{
  if(x==0)
  {
      putchar('0');putchar(y);
      return;
  }
  if(x<0)
  {
      putchar('-');
      x=-x;
  }
  static char wr[20];
  int top=0;
  for(;x;x/=10)wr[++top]=x%10+'0';
  while(top)putchar(wr[top--]);
  putchar(y);
}
void file()
{
  #ifndef ONLINE_JUDGE
      freopen("4710.in","r",stdin);
      freopen("4710.out","w",stdout);
  #endif
}
const int mo=1e9+7;
int n,m,a[N];
void input()
{
	n=read<int>(),m=read<int>();
	For(i,1,m)a[i]=read<int>();
}
int ans;
int C[2005][2005];
const int maxn=2e3;
void work()
{
	For(i,0,maxn)C[i][0]=C[i][i]=1;
	For(i,2,maxn)For(j,1,i-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	int sum;
	For(i,1,n)
	{
		sum=1;
		For(j,1,m)sum=1ll*sum*C[a[j]+i-1][i-1]%mo;
		if((n-i)&1)ans=(ans-1ll*sum*C[n][i]%mo+mo)%mo;
		else ans=(ans+1ll*sum*C[n][i]%mo)%mo;
	}
	write(ans,'
');
}
int main()
{
	file();
	input();
	work();
	return 0;
}
bzoj
  • 设(f[i])强制选择i个相同元素的方案数，(f[i]={achoose b}*(2^{2^{n-i}}-1)),注意计算上面指数要(\%(mod-1))，（WA了半天）,剩下就是个二项式容斥了
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i)
#define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i)
const int N=1e6+5;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
  T ans=0,f=1;
  char ch=getchar();
  while(!isdigit(ch)&&ch!='-')ch=getchar();
  if(ch=='-')f=-1,ch=getchar();
  while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
  return ans*f;
}
template<typename T>void write(T x,char y)
{
  if(x==0)
  {
      putchar('0');putchar(y);
      return;
  }
  if(x<0)
  {
      putchar('-');
      x=-x;
  }
  static char wr[20];
  int top=0;
  for(;x;x/=10)wr[++top]=x%10+'0';
  while(top)putchar(wr[top--]);
  putchar(y);
}
void file()
{
  #ifndef ONLINE_JUDGE
      freopen("2839.in","r",stdin);
      freopen("2839.out","w",stdout);
  #endif
}
const int mo=1e9+7;
int n,k;
void input()
{
	n=read<int>(),k=read<int>();
}
int pw[N],f[N],mc[N],inv[N];
ll power(ll x,int y)
{
	ll res=1;
	for(;y;x=x*x%mo,y>>=1)if(y&1)res=res*x%mo;
	return res;
}
int C(int n,int m)
{
	return 1ll*mc[n]*inv[m]%mo*inv[n-m]%mo;
}
void work()
{
	pw[0]=1;For(i,1,n)pw[i]=1ll*(pw[i-1]<<1)%mo;
	For(i,1,n)pw[i]=power(2,pw[i])-1;
	mc[0]=1;For(i,1,n)mc[i]=1ll*mc[i-1]*i%mo;
	inv[0]=1;inv[n]=power(mc[n],mo-2);
	Fordown(i,n-1,1)inv[i]=1ll*inv[i+1]*(i+1)%mo;
	For(i,k,n)f[i]=1ll*C(n,i)*pw[n-i]%mo;
	For(i,k+1,n)f[k]=(f[k]+1ll*f[i]*C(i,k)%mo*(((i-k)&1)?-1:1)%mo+mo)%mo;
	write(f[k],'
');
}
int main()
{
	file();
	input();
	work();
	return 0;
}
bzoj 4767
  • 首先解个方程，两个解就是两种方式所需要的步数，对于每个障碍点也算出两种方式所需要的步数，然后将解排序，用每个点的方案减去前面所有可以到达它的障碍点到它的方案即可。
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i)
#define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i)
const int N=500+5;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
  T ans=0,f=1;
  char ch=getchar();
  while(!isdigit(ch)&&ch!='-')ch=getchar();
  if(ch=='-')f=-1,ch=getchar();
  while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
  return ans*f;
}
template<typename T>void write(T x,char y)
{
  if(x==0)
  {
      putchar('0');putchar(y);
      return;
  }
  if(x<0)
  {
      putchar('-');
      x=-x;
  }
  static char wr[20];
  int top=0;
  for(;x;x/=10)wr[++top]=x%10+'0';
  while(top)putchar(wr[top--]);
  putchar(y);
}
void file()
{
  #ifndef ONLINE_JUDGE
      freopen("4767.in","r",stdin);
      freopen("4767.out","w",stdout);
  #endif
}
int A,B,n;
int ax,bx,ay,by;
void input()
{
	A=read<int>(),B=read<int>();n=read<int>();
	ax=read<int>(),ay=read<int>(),bx=read<int>(),by=read<int>();
}
void cal(int x1,int y1,int x2,int y2,int &t1,int &t2)
{
	int x=x2-x1,y=y2-y1;
	int temp=x*by-y*bx;
	int res=by*ax-ay*bx;
	if(temp%res!=0)t1=t2=-1;
	else
	{
		t1=temp/res;
		if(bx)
		{
			temp=x-ax*t1;
			if(temp%bx==0)t2=temp/bx;
			else t1=t2=-1;
		}
		else if(by)
		{
			temp=y-ay*t1;
			if(temp%by==0)t2=temp/by;
			else t1=t2=-1;
		}
	}
}
const int mo=1e9+7;
const int maxn=5e5;
int inv[maxn+5],mc[maxn+5];
ll power(ll x,int y)
{
	ll res=1;
	for(;y;x=x*x%mo,y>>=1)if(y&1)res=res*x%mo;
	return res;
}
void init()
{
	mc[0]=1;For(i,1,maxn)mc[i]=1ll*mc[i-1]*i%mo;
	inv[0]=1;inv[maxn]=power(mc[maxn],mo-2);
	Fordown(i,maxn-1,1)inv[i]=1ll*inv[i+1]*(i+1)%mo;
}
int C(int x,int y)
{
	if(x<y)return 0;
	return 1ll*mc[x]*inv[y]%mo*inv[x-y]%mo;	
}
int ans;
typedef pair<int,int> pii;
pii q[N];
int tot;
#define mk make_pair
#define fir first
#define sec second
void add(int &a,int b)
{
	a+=b;if(a>=mo)a-=mo;
}
int path(int i,int j)
{
	int x=q[j].fir-q[i].fir	,y=q[j].sec-q[i].sec;
	if(x<0||y<0)return 0;
	return C(x+y,y);
}
int dp[N];
void work()
{
	int t1,t2;
	cal(0,0,A,B,t1,t2);
	if(t1<0||t2<0){puts("0");return;}
	A=t1,B=t2;
	q[++tot]=mk(t1,t2);
	int x,y;
	For(i,1,n)
	{
		x=read<int>(),y=read<int>();
		cal(0,0,x,y,t1,t2);
		if(t1>=0&&t2>=0&&t1<=A&&t2<=B)q[++tot]=mk(t1,t2);
	}
	sort(q+1,q+tot+1);
	For(i,1,tot)
	{
		dp[i]=C(q[i].fir+q[i].sec,q[i].fir);
		For(j,1,i-1)add(dp[i],mo-1ll*dp[j]*path(j,i)%mo);
	}
	write(dp[tot],'
');
}
int main()
{
	file();
	input();
	init();
	work();
	return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/dengyixuan/p/8818624.html