容斥原理，多步容斥

限制$f_i$是难以求解的，去掉$f_i$的限制是好做的，很容易想到把它容斥掉。

容斥意义法：我们把选择$s$朵花看做总限制，对第$i$个花瓶的限制设出集合，则$S_i$表示满足总共选了$s$朵花，并且第$i$个花瓶的花$\le f_i$的方案的集合，则答案为$\left|\underset{i=1}{\bigcap ^n}{S}_i\right|$，容易想到用容斥原理来求解。
则：$\left|\underset{i=1}{\bigcap ^n}{S}_i\right|=\sum _{T\subseteq [n]}(-1{)}^{|T|}\left|\bigcap _{i\in T}\overline{S_i}\right|$，对于$T$，我们要求出限制$i\in T$均不合法的方案数，则我们指定物品$i$至少选择了$f_i+1$次，剩下的次数为$s-\sum _{i\in T}(f_i+1)$，我们将它们划分到$n$个花瓶中，根据集合的定义，我们不需要管这些花瓶的限制，这是隔板法问题，即$\left(\begin{array}{c}s-\sum _{i\in T}(f_i+1)+n-1\\ n-1\end{array}\right)$。因此最终的式子就是：$\left|\underset{i=1}{\bigcap ^n}{S}_i\right|=\sum _{T\subseteq [n]}(-1{)}^{|T|}\left(\begin{array}{c}s-\sum _{i\in T}(f_i+1)+n-1\\ n-1\end{array}\right)$

注：部分题解当中提到了“多重集的组合数”，很容易看成是“多重组合数”，但其实两者没啥关系。

代码（值域很大的组合数很难直接求解，我们把组合数转化为下降幂求解）：

#include<iostream>
using namespace std;
const int N=20;
const long long M=1e9+7;
long long pow(long long a,long long b,long long c) {long long ans=1;while(b) {if(b&1) (ans=ans*a)%=M;(a=a*a)%=M;b>>=1;}return ans;
}
long long inv(long long x) {return pow(x,M-2,M);
}
long long a[N+5];
int n;
long long m;
long long d(long long x,long long k) {if(k==0) return 1;else return x%M*d(x-1,k-1)%M;
} 
long long calc(int s) {long long sum=0;for(int i=1;i<=n;i++) if(s>>i-1&1) sum+=a[i]+1;if(m-sum<0) return 0;return d(m-sum+n-1,n-1)*inv(d(n-1,n-1))%M;
} 
int main() {cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];long long ans=0;for(int s=0;s<1<<n;s++) (ans+=calc(s)*(__builtin_popcount(s)&1?-1:1))%=M;cout<<(ans%M+M)%M;
}

容易想到把$d_i$容斥掉。

容斥意义：我们把购买了价值为$s$的物品作为总限制，把对硬币$i$的数量的限制作为集合，则设$S_i$表示满足对第$i$个硬币数量限制，且购买了价值为$s$的物品的方案的集合，则答案为$\left|\underset{i=1}{\bigcap ^4}{S}_i\right|$，接下来根据$\left|\underset{i=1}{\bigcap ^n}{S}_i\right|=\sum _{T\subseteq [n]}(-1{)}^{|T|}\left|\bigcap _{i\in T}\overline{S_i}\right|$，我们要求解补集的交，即对于一些硬币的限制不满足的方案数。
如果硬币$i\in T$的限制不满足，显然它选了至少$d_i+1$个，我们提前dp出$f_x$表示购买了价值为$s$物品的完全背包方案数，则此时的方案数量为$f_{s-\sum _{i\in T}(d_i+1)}$。

则本次询问的答案为：$\left|\underset{i=1}{\bigcap ^4}{S}_i\right|=\sum _{T\subseteq [4]}(-1{)}^{|T|}{f}_{s-\sum _{i\in T}(d_i+1)}$

每做一次询问，我们就进行一次容斥，复杂度为$O(2^4)$，因此总复杂度为$(n\cdot 2^4)$

#include<iostream>
#include<algorithm>
using namespace std;
const int R=100000;
long long f[R+5];
int a[10],b[10];
long long calc(int s,int x) {int t=1;while(s) x-=(s&1)*a[t]*(b[t]+1),s>>=1,t++;if(x<0) return 0;else return f[x];
}
int main() {int n;cin>>a[1]>>a[2]>>a[3]>>a[4]>>n;f[0]=1;for(int i=1;i<=4;i++)for(int j=a[i];j<=R;j++) f[j]+=f[j-a[i]];while(n--) {int x;cin>>b[1]>>b[2]>>b[3]>>b[4]>>x;long long ans=0;for(int i=0;i<1<<4;i++) ans+=calc(i,x)*(__builtin_popcount(i)&1?-1:1);
//		cout<<"***";cout<<ans<<endl;}
}

将 k 个棋子放在 $n\times m$ 的棋盘上。我们将连续的紧贴棋盘边界的放置棋子位置称为边缘。问上下左右四个边缘上都至少放置一个棋子的棋子放置方案共有多少种.
可以做到$n\times m\le 10^5,k\le 10^5$

容斥意义：我们总共四个边缘，我们设$S_i$表示第$i$个边缘有棋子的所有方案构成的集合，则答案为$\left|\bigcap S\right|$，求解补集相当于指定一些边缘没有棋子，剩下位置随意，容斥原理求解即可。

题意简述：给出一个具有$n$个元素的数组和一个整数$m$，求出$[1,m]$中有多少个数至少能整除$a$数组中的一个数。
$n\le 10,a_i,m\le 2^{31}$

可以想到，能够整除$x$的数的数量为${\sigma }_0(x)$，能够整除$y$的数量为${\sigma }_0(y)$，还要在减去算重的数量，也就是既整除$x$又整除$y$的数，数量为${\sigma }_0(\gcd (x,y))$
其中${\sigma }_0$表示约数个数函数。

容斥意义：我们把值域为$[1,m]$作为总限制，对“能够整除$a_i$”设计集合，则$S_i$表示能够整除$a_i$的数的集合，答案为$\left|\underset{i=1}{\bigcup ^n}{S}_i\right|$，则我们根据$\left|\underset{i=1}{\bigcup ^n}{S}_i\right|=\sum _{\varnothing \ne T\subseteq [n]}(-1{)}^{|T|-1}\left|\bigcap _{i\in T}{S}_i\right|$，只需要求解集合的交即可。
也就是对于$T$来说，求出是所有能够整除$i\in T$的数的数量，也就是 σ 0 ( gcd ⁡ i ∈ T { a i } ) \sigma_0\left({\underset{i\in T}\gcd \{a_i\}}\right) σ0​(i∈Tgcd​{ai​})，因此答案为 ∣ ⋃ n i = 1 S i ∣ = ∑ ∅ ≠ T ⊆ [ n ] ( − 1 ) ∣ T ∣ − 1 σ 0 ( gcd ⁡ i ∈ T { a i } ) \left|\underset{i=1}{\overset{n}{\bigcup}}S_i \right|={\underset{\varnothing\not=T\subseteq [n]}{\overset{}\sum}}(-1)^{|T|-1}\sigma_0\left({\underset{i\in T}\gcd \{a_i\}}\right) ​i=1⋃n​​Si​ ​=∅=T⊆[n]∑​​(−1)∣T∣−1σ0​(i∈Tgcd​{ai​})
约数个数函数可以通过预处理质因子等手段求出。

时间复杂度为$O(2^n)$

这个题还可以子集反演，本质上是一样的。不过这个题完全可以直接容斥。

我们要建立一个从树节点到图节点的映射$f$，使得$f$为一个双射，这是不好限制的，我们把它转化为，$f$共有$n$个不同的像。

那我们设$S_i$表示第$i$个图节点是像的方案的集合，则答案为$\left|\underset{i=1}{\bigcap ^n}{S}_i\right|=\sum _{T\subseteq [n]}(-1{)}^{|T|}\left|\bigcap _{i\in T}\overline{S_i}\right|$，这样$T$相当于求解指定一些图节点不能使用，剩下的节点随便。

设$s=[n]\oplus T$，此时这个交集的大小是可以树形dp出来的，设$f_{u,i}$表示dp到了树节点$u$，节点$u$对应图节点$i$的方案数，则转移就是，对于$u$的儿子$v$对应的图节点为$j$，只要$(i,j)$在图上有连边，并且$i,j\in s$，就可以转移：

void dfs(int u,int fa) {for(int v=1;v<=n;v++)if(b[u][v]&&(v^fa)) {dfs(v,u);for(int i=1; i<=n; i++)if(s>>i-1&1) {long long sum=0;for(int j=1; j<=n; j++)if(s>>j-1&1)if(a[i][j])sum+=f[v][j];f[u][i]*=sum;}}
}

显然初值为$f_{u,i\in s}=1$