容斥原理

意义：有些问题中经常会出现这样一些烦人的限制条件如: 每个物品有一个额外的权如 1101 , 1001 ， 我们最终答案的状态种一定要满足所取的物品，它们的权或后为 1111 。此时如果这个值的位数很大我们之前学习过的知识对其就没有办法了。此时我们不妨分析一下最终的答案是怎么得到的。只要最终四个位上都有 1 就满足了对吧，不难发现如果我们把条件放宽一点：即最终得到的答案是1111的子集，满足这样条件的状态很好求吧。（废话。。无论怎么取都成立的好不好。。）如图： 我们发现对于 S[1111] 绿色框中的元素是多余的。我们需要把它删了只剩 (1,2,3,4) 盗用一下小C的图片。。。 ans（1,2,3,4）=S[1111]−（S[1110]+S[1101]+S[1011]+S[0111]）+（S[0110]+S[1001]+S[1010]+S[0101]+S[1100]+S[0011]）−（S[1000]+S[0100]+S[0010]+S[0001]）

子集的枚举

在更多问题中，我们都可能需要枚举某个集合的子集，但是其时间复杂度往往因为算法的不同有很大的差别，所以学习一下它也是很重要的。先说说比较基础的版本：枚举时把 j=j & i 直接跳到下一个有用的集合而不是一个一个枚举最后判。 /*时间复杂度：3^m*/ for(int i=(1<<m)-1;i;--i) /*枚举所有的子集时直接跳到下一个有用的集合中*/ for(int j=(i-1)&i;j;j=(j-1)&i) collect(i,j);/*把子集j的信息收集给i*/ 同样还有一个也比较好记的版本：我们用j1<<i去更新去更新 j 但要注意两层循环的顺序。 /*复杂度 M*2^M*/ for(int i=0;i<m;i ) for(int j=0;j<1<<m;j ) if(j&1<<i)collect(j,j^1<<i);

例题

礼物沙龙

仔细发现发现S[t]=2cntt cntt 表示集合 t <script type="math/tex" id="MathJax-Element-15">t</script>的子集数。那么我们直接利用上面讲两个技巧即可。 #include<bits/stdc++.h> using namespace std; const int N=1<<21,P=1e9+7; int b[N],B[N],C[N],n,m,ans; int val(int x){ int cnt=0; while(x)x-=x&-x,cnt++; return cnt; } int main(){ scanf("%d%d",&n,&m);B[0]=1; for(int i=1;i<=n;i++)B[i]=1ll*(B[i-1]<<1)%P; for(int i=1,t,x,s;i<=n;++i){ scanf("%d",&t);s=0; while(t--)scanf("%d",&x),s|=1<<x-1; ++b[s]; } /*子集枚举*/ for(int i=0;i<m;i++) for(int j=0;j<1<<m;j++) if(j&1<<i)b[j]+=b[j^1<<i]; /*容斥即可*/ for(int i=0;i<(1<<m);++i){ if((val(i)&1)==(m&1))ans=(ans+B[b[i]])%P; else ans=(ans-B[b[i]]+P)%P; } printf("%d\n",ans); return 0; }

暴力的数论

再举一个例子，该题中我们需要计算x以内不包含比p小的素因子的正整数个数，就可以利用容斥原理。 #include<bits/stdc++.h> using namespace std; const int C=50,MAX=1e9; typedef long long ll; int n,p,tot,pri[C]; bool mark[MAX/C]; inline int calc(int x){ /* 计算x以内不包含比p小的素因子的正整数个数 对应一个p有a1,a2...a tot个比p小的质因子，我们把所有ai构成的数都去掉此时我们需要通过容斥 用二进制枚举一个集合S t= ∏ai*(S&1<<i);num-=x/t 但是一些数会被重复减到，我们发现如果如果集合中有奇数个元素x/t取正，反之取负 */ int res=x; for(int S=1;S<1<<tot;++S){//枚举加容斥 int t=1,f=-1; for(int i=0;i<tot;++i)if(S&1<<i)t*=pri[i],f*=-1; res-=f*x/t; }return res; } inline int S1(){ for(int i=2;i<p;++i)if(!mark[i]){ pri[tot++]=i; for(int j=i*i;j<p;j+=i)mark[j]=1; } int L=1,R=MAX/p,res; while(L<=R){ int mid=L+R>>1,t=calc(mid); if(t==n)res=mid,R=mid-1; else if(t<n)L=mid+1; else R=mid-1; //找满足calc(mid)==n的最小的mid,而calc()单调不递减的 } if(calc(res)!=n)return 0; return res*p; } inline int S2(){ if(n==1)return p; memset(mark,1,sizeof(mark)); int mx=MAX/p; for(int i=2,cnt=1;i<=mx;++i){ if(mark[i]){ if(i<p)for(ll j=i*i;j<=mx;j+=i)mark[j]=0; else if(++cnt==n)return i*p;//无需再用mark来记录了 } }return 0; } int main(){ scanf("%d%d",&n,&p); printf("%d\n",p<50?S1():S2()); return 0; }

XB的生日

该题中满足最后一定要买齐4个物品的条件就可以使用容斥来实现。