容斥
計算公式
設集合為 
使用場景
容斥原理常用於集合計數問題。
而枚舉集合則可以用二進制枚舉。設共有 \(n\) 個集合，那麼可以用 \(2^n\) 的時間複雜度枚舉所有可能的集合組合。顯然要求是 \(n\)
注意到基本上容斥的係數為 \(\pm 1\) 與枚舉的集合組合的集合個數的奇偶性有關，所以可以設計一個函數專門用來計算一個數（二進制枚舉）二進制下的 \(1\)
詳細地，給份枚舉集合組合的代碼。
int num1(int s)//計算s在二進制下的1的個數
{
int ans=0;
while(s){if(s&1)++ans;s>>=1;}
return ans;
}
void Main()
{
FUP(base,1,(1<<n)-1)//這裏一共有n個集合
{
ljl opt=(num1(base)&1?-1ll:1ll),cnt=0ll;//這裏的+-1因題而異
FUP(i,0,n-1)
if((base>>i)&1)
cnt+=g(i+1);//注意是i+1
if(s>=cnt)ans=ans+opt*(ljl_is_vegetable);
//在上面 ljl_is_vegetable 處填入集合的值。每題都不一樣。
}
return;
}例題
洛谷 P1450 [HAOI2008] 硬幣購物
先考慮簡單版的題目。即沒有 \(d_i\)
不難想到做一個完全揹包，令 \(f_i\) 表示用所有面值的硬幣湊成 \(i\)
那麼考慮只有一個硬幣，且它的限制為 \(d_i\)。
注意到狀態轉移方程為 \(f_j\leftarrow f_j+f_{j-c_i}\)。而其中可能存在不合法的方案。即用了大於 \(d_i\) 個 \(c_i\)。
那麼是不是所有 \(a+t\cdot c_i=s,t>d_i\) 的都是不合法的，我們只需要 \(s-c_i\cdot \min\left\{t\mid t>d_i\right \}\)，即 \(t=d_i+1\)
換句話説，我們需要從不合法方案 \(s\) 中剔除至少 \(d_i+1\) 個 \(c_i\)，即 \(s-(d_i+1)c_i\)。所得的都是不合法的，要減掉。即減掉 \(f_{s-(d_i+1)\cdot c_i}\)。
所以就可以抽象成一個文氏圖。
由於作者很菜很懶，所以用只有 \(2\)
上文中的對於 \(i\) 號硬幣不合法可以理解為用了至少 \(d_i+1\)
我們設左邊的圈為 \(S_1\)，右邊的為 \(S_2\)，全集為 \(C\)。
那麼
對於多個集合也是同理。
那麼再運用上剛説的集合枚舉，就可以寫出代碼：
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
#define FUP(i,x,y) for(int i=(x);i<=(y);++i)
#define FDW(i,x,y) for(int i=(x);i>=(y);--i)
const int S=1e5+5;
int T;
ljl f[S],ans,c[5],d[5],s;
ljl g(int x){return (ljl)c[x]*(d[x]+1);}
int num1(int s)
{
int ans=0;
while(s){if(s&1)++ans;s>>=1;}
return ans;
}
void Main()
{
FUP(i,1,4) cin>>d[i];
cin>>s;ans=f[s];
// cout<<"ans="<<ans<<'\n';
FUP(base,1,(1<<4)-1)
{
//1-2+
// cout<<"base "<<base<<'\n';
ljl opt=(num1(base)&1?-1ll:1ll),cnt=0ll;
// cout<<"opt="<<opt<<'\n';
FUP(i,0,3)
if((base>>i)&1)
cnt+=g(i+1);
if(s>=cnt)ans=ans+opt*f[s-cnt];
}
cout<<ans<<'\n';
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
FUP(i,1,4)cin>>c[i];
cin>>T;f[0]=1ll;
FUP(i,1,4)
FUP(j,c[i],100000)
f[j]+=f[j-c[i]];
while(T--)
Main();
return 0;
}