长沙手机网站设计,响应式网站原理,wordpress自媒体主题更新失败,大连手机自适应网站建设维护容斥意义法 设计状态表示容斥的过程。比较简单的容斥题目一般可以容斥意义。 如果我们要求方案数的话#xff0c;通常情况下我们的把限制视为两个方面#xff0c;一方面是总限制#xff0c;一方面是对于每个物品的限制#xff0c;这样设集合 S i S_i Si表示满足总限制以及…容斥意义法 设计状态表示容斥的过程。比较简单的容斥题目一般可以容斥意义。 如果我们要求方案数的话通常情况下我们的把限制视为两个方面一方面是总限制一方面是对于每个物品的限制这样设集合 S i S_i Si表示满足总限制以及对第 i i i个限制的方案构成的集合若答案为 ∣ ⋃ n i 1 S i ∣ \left| {\underset{i1}{\overset{n}\bigcup}}S_i\right| i1⋃nSi 或 ∣ ⋂ n i 1 S i ∣ \left| {\underset{i1}{\overset{n}\bigcap}}S_i\right| i1⋂nSi 则可以使用容斥原理求解。容斥符号法 如果认为这个题是容斥并且没什么太好的容斥想法可以尝试容斥符号例如把 为 ≤ \leq ≤或 ≥ \geq ≥ 为 ⊆ , ⊇ \subseteq,\supseteq ⊆,⊇例如把双射容斥为子集 ⊂ \subset ⊂为 ⊆ \subseteq ⊆修正法 可以先编一个错误的答案然后再考虑如何容斥掉多余的部分。很多较为复杂的题都可以修正。
容斥原理
一般的容斥原理就是设出集合使得集合的并/交为答案然后利用容斥原理求解的过程。 如果设不出集合或者难以求解则可以考虑更加复杂的计数方式例如反演。
容斥原理 补集转换 : S U − S ‾ 补集转换:SU-\overline{ S} 补集转换:SU−S 德 ⋅ 摩根定律 : ⋃ n i 1 S i ‾ ⋂ n i 1 S i ‾ , ⋂ n i 1 S i ‾ ⋃ n i 1 S i ‾ 德·摩根定律:\overline{\underset{i1}{\overset{n}{\bigcup}}S_i}\underset{i1}{\overset{n}{\bigcap}}\overline{S_i},\overline{\underset{i1}{\overset{n}{\bigcap}}S_i }\underset{i1}{\overset{n}{\bigcup}}\overline{S_i} 德⋅摩根定律:i1⋃nSii1⋂nSi,i1⋂nSii1⋃nSi 集合的并 : ∣ ⋃ n i 1 S i ∣ ∑ ∅ ̸ T ⊆ [ n ] ( − 1 ) ∣ T ∣ − 1 ∣ ⋂ i ∈ T S i ∣ 集合的并:\left|\underset{i1}{\overset{n}{\bigcup}}S_i \right|{\underset{\varnothing\notT\subseteq [n]}{\overset{}\sum}}(-1)^{|T|-1}\left |{\underset{i\in T}{\overset{}\bigcap}}S_i\right | 集合的并: i1⋃nSi ∅T⊆[n]∑(−1)∣T∣−1 i∈T⋂Si 集合的交 : ∣ ⋂ n i 1 S i ∣ ∑ T ⊆ [ n ] ( − 1 ) ∣ T ∣ ∣ ⋂ i ∈ T S i ‾ ∣ 集合的交:\left| {\underset{i1}{\overset{n}\bigcap}}S_i\right|{\underset{T\subseteq [n]}{\overset{}\sum}}(-1)^{|T|}\left|{\underset{i\in T}{\bigcap}\overline{S_i}}\right| 集合的交: i1⋂nSi T⊆[n]∑(−1)∣T∣ i∈T⋂Si
事实上求解集合的交的式子是由两步构成根据德·摩根定律 ∣ ⋂ n i 1 S i ∣ U − ∣ ⋃ n i 1 S i ‾ ∣ \left| {\underset{i1}{\overset{n}\bigcap}}S_i\right|U-\left| {\underset{i1}{\overset{n}\bigcup}}\overline{S_i}\right| i1⋂nSi U− i1⋃nSi 这说明集合的交全集-补集的并但是并集往往都比交集更难求解除非集合之间没有交时并集才好求解但是我们在求解补集的并时如果各个补集之间没有交说明原集的并为全集这样就不用求解了因此我们注意到 ∣ ⋃ n i 1 S i ‾ ∣ \left| {\underset{i1}{\overset{n}\bigcup}}\overline{S_i}\right| i1⋃nSi 也是集合的交集的形式因此我们套用容斥原理进行求解这样的过程叫做有人称为多步容斥。
补集转化
补集转化较简单。
有标号连通图计数
求 n n n个节点的无向连通图有多少个节点有标号编号为 [ 1 , n ] [1,n] [1,n] n 5000 n5000 n5000
这个题是朴素容斥即考虑如何用容斥原理来修正答案。
设 f i f_i fi表示大小为 i i i的连通图数量一个想法是首先连出一棵树但是不太好搞考虑补集转换总边数为 i ( i − 1 ) 2 \frac{i(i-1)}2 2i(i−1)总可能性为 h ( i ) 2 i ( i − 1 ) 2 h(i)2^{\frac {i(i-1)}2} h(i)22i(i−1)种减去不连通的情况即可那我们枚举 1 1 1号点所在的连通块大小 j j j然后从剩下的 i − 1 i-1 i−1个点中选出 j − 1 j-1 j−1个点情况数量为 f j ( i − 1 j − 1 ) f_j \begin{pmatrix}i-1\\ j-1\end{pmatrix} fj(i−1j−1)剩下 i − j i-j i−j个点随意连边转移方程为 f i h ( i ) − ∑ j i f j ( i − 1 j − 1 ) h ( i − j ) f_ih(i)-\underset{ji}\sum f_j \begin{pmatrix}i-1\\ j-1\end{pmatrix}h(i-j) fih(i)−ji∑fj(i−1j−1)h(i−j)
集合的交
容斥原理求解集合的交比较多求解并反而比较少因为题目往往要求同时遵守所有限制而不是只遵守其中一个这符合交的形式。
CF451E
限制 f i f_i fi是难以求解的去掉 f i f_i fi的限制是好做的很容易想到把它容斥掉。
容斥意义法我们把选择 s s s朵花看做总限制对第 i i i个花瓶的限制设出集合则 S i S_i Si表示满足总共选了 s s s朵花并且第 i i i个花瓶的花 ≤ f i \leq f_i ≤fi的方案的集合则答案为 ∣ ⋂ n i 1 S i ∣ \left| {\underset{i1}{\overset{n}\bigcap}}S_i\right| i1⋂nSi 容易想到用容斥原理来求解。 则 ∣ ⋂ n i 1 S i ∣ ∑ T ⊆ [ n ] ( − 1 ) ∣ T ∣ ∣ ⋂ i ∈ T S i ‾ ∣ \left| {\underset{i1}{\overset{n}\bigcap}}S_i\right|{\underset{T\subseteq [n]}{\overset{}\sum}}(-1)^{|T|}\left|{\underset{i\in T}{\bigcap}\overline{S_i}}\right| i1⋂nSi T⊆[n]∑(−1)∣T∣ i∈T⋂Si 对于 T T T我们要求出限制 i ∈ T i\in T i∈T均不合法的方案数则我们指定物品 i i i至少选择了 f i 1 f_i1 fi1次剩下的次数为 s − ∑ i ∈ T ( f i 1 ) s-\underset{i\in T}\sum (f_i1) s−i∈T∑(fi1)我们将它们划分到 n n n个花瓶中根据集合的定义我们不需要管这些花瓶的限制这是隔板法问题即 ( s − ∑ i ∈ T ( f i 1 ) n − 1 n − 1 ) \begin{pmatrix}s-\underset{i\in T}\sum (f_i1)n-1\\n-1\end{pmatrix} (s−i∈T∑(fi1)n−1n−1)。因此最终的式子就是 ∣ ⋂ n i 1 S i ∣ ∑ T ⊆ [ n ] ( − 1 ) ∣ T ∣ ( s − ∑ i ∈ T ( f i 1 ) n − 1 n − 1 ) \left| {\underset{i1}{\overset{n}\bigcap}}S_i\right|{\underset{T\subseteq [n]}{\overset{}\sum}}(-1)^{|T|}\begin{pmatrix}s-\underset{i\in T}\sum (f_i1)n-1\\n-1\end{pmatrix} i1⋂nSi T⊆[n]∑(−1)∣T∣(s−i∈T∑(fi1)n−1n−1)
注部分题解当中提到了“多重集的组合数”很容易看成是“多重组合数”但其实两者没啥关系。
代码值域很大的组合数很难直接求解我们把组合数转化为下降幂求解
#includeiostream
using namespace std;
const int N20;
const long long M1e97;
long long pow(long long a,long long b,long long c) {long long ans1;while(b) {if(b1) (ansans*a)%M;(aa*a)%M;b1;}return ans;
}
long long inv(long long x) {return pow(x,M-2,M);
}
long long a[N5];
int n;
long long m;
long long d(long long x,long long k) {if(k0) return 1;else return x%M*d(x-1,k-1)%M;
}
long long calc(int s) {long long sum0;for(int i1;in;i) if(si-11) suma[i]1;if(m-sum0) return 0;return d(m-sumn-1,n-1)*inv(d(n-1,n-1))%M;
}
int main() {cinnm;for(int i1;in;i) cina[i];long long ans0;for(int s0;s1n;s) (anscalc(s)*(__builtin_popcount(s)1?-1:1))%M;cout(ans%MM)%M;
}P1450
容易想到把 d i d_i di容斥掉。
容斥意义我们把购买了价值为 s s s的物品作为总限制把对硬币 i i i的数量的限制作为集合则设 S i S_i Si表示满足对第 i i i个硬币数量限制且购买了价值为 s s s的物品的方案的集合则答案为 ∣ ⋂ 4 i 1 S i ∣ \left| {\underset{i1}{\overset{4}\bigcap}}S_i\right| i1⋂4Si 接下来根据 ∣ ⋂ n i 1 S i ∣ ∑ T ⊆ [ n ] ( − 1 ) ∣ T ∣ ∣ ⋂ i ∈ T S i ‾ ∣ \left| {\underset{i1}{\overset{n}\bigcap}}S_i\right|{\underset{T\subseteq [n]}{\overset{}\sum}}(-1)^{|T|}\left|{\underset{i\in T}{\bigcap}\overline{S_i}}\right| i1⋂nSi T⊆[n]∑(−1)∣T∣ i∈T⋂Si 我们要求解补集的交即对于一些硬币的限制不满足的方案数。 如果硬币 i ∈ T i\in T i∈T的限制不满足显然它选了至少 d i 1 d_i1 di1个我们提前dp出 f x f_x fx表示购买了价值为 s s s物品的完全背包方案数则此时的方案数量为 f s − ∑ i ∈ T ( d i 1 ) f_{s-\underset{i\in T}\sum(d_i1)} fs−i∈T∑(di1)。
则本次询问的答案为 ∣ ⋂ 4 i 1 S i ∣ ∑ T ⊆ [ 4 ] ( − 1 ) ∣ T ∣ f s − ∑ i ∈ T ( d i 1 ) \left| {\underset{i1}{\overset{4}\bigcap}}S_i\right|{\underset{T\subseteq [4]}{\overset{}\sum}}(-1)^{|T|}f_{s-\underset{i\in T}\sum(d_i1)} i1⋂4Si T⊆[4]∑(−1)∣T∣fs−i∈T∑(di1)
每做一次询问我们就进行一次容斥复杂度为 O ( 2 4 ) O(2^4) O(24)因此总复杂度为 ( n ⋅ 2 4 ) (n\cdot 2^4) (n⋅24)
#includeiostream
#includealgorithm
using namespace std;
const int R100000;
long long f[R5];
int a[10],b[10];
long long calc(int s,int x) {int t1;while(s) x-(s1)*a[t]*(b[t]1),s1,t;if(x0) return 0;else return f[x];
}
int main() {int n;cina[1]a[2]a[3]a[4]n;f[0]1;for(int i1;i4;i)for(int ja[i];jR;j) f[j]f[j-a[i]];while(n--) {int x;cinb[1]b[2]b[3]b[4]x;long long ans0;for(int i0;i14;i) anscalc(i,x)*(__builtin_popcount(i)1?-1:1);
// cout***;coutansendl;}
}UVA11806
将 k 个棋子放在 n × m n\times m n×m 的棋盘上。我们将连续的紧贴棋盘边界的放置棋子位置称为边缘。问上下左右四个边缘上都至少放置一个棋子的棋子放置方案共有多少种. 可以做到 n × m ≤ 1 0 5 , k ≤ 1 0 5 n\times m\leq 10^5,k\leq 10^5 n×m≤105,k≤105
容斥意义我们总共四个边缘我们设 S i S_i Si表示第 i i i个边缘有棋子的所有方案构成的集合则答案为 ∣ ⋂ S ∣ \left|\bigcap S\right| ∣⋂S∣求解补集相当于指定一些边缘没有棋子剩下位置随意容斥原理求解即可。
互质问题1
给出一个整数 n n n和一个整数 m m m求 [ 1 , m ] [1,m] [1,m]之中有多少个数与 n n n互质。 1 ≤ n , m ≤ 1 0 18 1\leq n,m\leq 10^{18} 1≤n,m≤1018
首先我们会分析出来如果与 n n n互质则说明这个数不含有 n n n的任何一个质因子因此可以容斥意义设 S i S_i Si表示 [ 1 , m ] [1,m] [1,m]中不含有 n n n的第 i i i个本质不同质因子的数的集合则答案为 ∣ ⋂ S i ∣ |\bigcap S_i| ∣⋂Si∣对应的 T T T相当于求出 [ 1 , m ] [1,m] [1,m]之中有多少个数含有质因子集合 T T T则方案数为 ⌊ m ∏ i ∈ T p i ⌋ \left\lfloor\frac m{\underset{i\in T}\prod p_i}\right\rfloor ⌊i∈T∏pim⌋。
这个容斥的时间复杂度为 O ( 2 ∣ P ∣ ) O\left(2^{|P|}\right) O(2∣P∣)其中 P P P表示 n n n的本质不同质因子构成的集合则 ∣ P ∣ O ( ln ln n ) |P|O(\ln\ln n) ∣P∣O(lnlnn)
互质问题2
给出一个整数 m m m一个具有 n n n个元素的数组求出 [ 1 , m ] [1,m] [1,m]中有多少个数与 n n n的所有元素互质 n ≤ 20 , m ≤ 2 62 n\leq 20,m\leq 2^{62} n≤20,m≤262
首先会考虑到与 n n n中所有元素互质相当于没有 n n n中任何一个元素的任何一个质因子因此我们可以将求出 n n n中的本质不同质因子集合设为 P P P则问题转化为求出 [ 1 , n ] [1,n] [1,n]当中有多少个数与 ∏ P \prod P ∏P互质。
POJ1091
给定 n n n个数其数值取值范围为 [ 1 , m ] [1,m] [1,m]请问有多少种情况使得这 n n n个数与 m m m的最大公约数为 1 1 1。 n , m 1 0 5 n,m10^5 n,m105
相当于对序列计数满足 { a n } , a i ∈ [ 1 , m ] , gcd ( gcd n i 1 { a i } , m ) 1 \{a_n\},a_i\in[1,m],\gcd\left(\underset{i1}{\overset n\gcd}\{a_i\},m\right)1 {an},ai∈[1,m],gcd(i1gcdn{ai},m)1
我们会发现如果序列的 gcd \gcd gcd与 m m m不互质说明它含有 m m m的某些质因子则说明序列中的每个数都含有这些质因子。因此我们可以用容斥意义来做这个题设 S i S_i Si表示 m m m的第 i i i个本质不同质因子不出现在序列最大公约数的方案的集合则答案为 ∣ ⋂ S i ∣ |\bigcap S_i| ∣⋂Si∣那么补集为指定 m m m的质因子集合的子集 T T T是序列每一个元素的约数也就是说序列每一个数都是 ∏ i ∈ T p i \underset{i\in T}\prod p_i i∈T∏pi的倍数那这样的序列共有 ⌊ m ∏ i ∈ T p i ⌋ n \left\lfloor\frac m{\underset{i\in T}\prod p_i}\right\rfloor^n ⌊i∈T∏pim⌋n容斥原理求解即可。
集合的并
HDU1796
题意简述给出一个具有 n n n个元素的数组和一个整数 m m m求出 [ 1 , m ] [1,m] [1,m]中有多少个数至少能整除 a a a数组中的一个数。 n ≤ 10 , a i , m ≤ 2 31 n\leq 10,a_i,m\leq 2^{31} n≤10,ai,m≤231
可以想到能够整除 x x x的数的数量为 σ 0 ( x ) \sigma_0(x) σ0(x)能够整除 y y y的数量为 σ 0 ( y ) \sigma_0(y) σ0(y)还要在减去算重的数量也就是既整除 x x x又整除 y y y的数数量为 σ 0 ( gcd ( x , y ) ) \sigma_0(\gcd(x,y)) σ0(gcd(x,y)) 其中 σ 0 \sigma_0 σ0表示约数个数函数。
容斥意义我们把值域为 [ 1 , m ] [1,m] [1,m]作为总限制对“能够整除 a i a_i ai”设计集合则 S i S_i Si表示能够整除 a i a_i ai的数的集合答案为 ∣ ⋃ n i 1 S i ∣ \left|\underset{i1}{\overset{n}{\bigcup}}S_i \right| i1⋃nSi 则我们根据 ∣ ⋃ n i 1 S i ∣ ∑ ∅ ̸ T ⊆ [ n ] ( − 1 ) ∣ T ∣ − 1 ∣ ⋂ i ∈ T S i ∣ \left|\underset{i1}{\overset{n}{\bigcup}}S_i \right|{\underset{\varnothing\notT\subseteq [n]}{\overset{}\sum}}(-1)^{|T|-1}\left |{\underset{i\in T}{\overset{}\bigcap}}S_i\right | i1⋃nSi ∅T⊆[n]∑(−1)∣T∣−1 i∈T⋂Si 只需要求解集合的交即可。 也就是对于 T T T来说求出是所有能够整除 i ∈ T i\in T i∈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{i1}{\overset{n}{\bigcup}}S_i \right|{\underset{\varnothing\notT\subseteq [n]}{\overset{}\sum}}(-1)^{|T|-1}\sigma_0\left({\underset{i\in T}\gcd \{a_i\}}\right) i1⋃nSi ∅T⊆[n]∑(−1)∣T∣−1σ0(i∈Tgcd{ai}) 约数个数函数可以通过预处理质因子等手段求出。
时间复杂度为 O ( 2 n ) O(2^n) O(2n)
P3349
这个题还可以子集反演本质上是一样的。不过这个题完全可以直接容斥。
我们要建立一个从树节点到图节点的映射 f f f使得 f f f为一个双射这是不好限制的我们把它转化为 f f f共有 n n n个不同的像。
那我们设 S i S_i Si表示第 i i i个图节点是像的方案的集合则答案为 ∣ ⋂ n i 1 S i ∣ ∑ T ⊆ [ n ] ( − 1 ) ∣ T ∣ ∣ ⋂ i ∈ T S i ‾ ∣ \left| {\underset{i1}{\overset{n}\bigcap}}S_i\right|{\underset{T\subseteq [n]}{\overset{}\sum}}(-1)^{|T|}\left|{\underset{i\in T}{\bigcap}\overline{S_i}}\right| i1⋂nSi T⊆[n]∑(−1)∣T∣ i∈T⋂Si 这样 T T T相当于求解指定一些图节点不能使用剩下的节点随便。
设 s [ n ] ⊕ T s[n]\oplus T s[n]⊕T此时这个交集的大小是可以树形dp出来的设 f u , i f_{u,i} fu,i表示dp到了树节点 u u u节点 u u u对应图节点 i i i的方案数则转移就是对于 u u u的儿子 v v v对应的图节点为 j j j只要 ( i , j ) (i,j) (i,j)在图上有连边并且 i , j ∈ s i,j\in s i,j∈s就可以转移
void dfs(int u,int fa) {for(int v1;vn;v)if(b[u][v](v^fa)) {dfs(v,u);for(int i1; in; i)if(si-11) {long long sum0;for(int j1; jn; j)if(sj-11)if(a[i][j])sumf[v][j];f[u][i]*sum;}}
}显然初值为 f u , i ∈ s 1 f_{u,i\in s}1 fu,i∈s1
模拟赛题 其中 n ≤ 20 , m ≤ 150 , k ≤ 7 , d ≤ 1 0 9 n\leq 20,m\leq 150,k\leq 7,d\leq 10^9 n≤20,m≤150,k≤7,d≤109
这个形式看起来非常的容斥首先考虑没有 k k k的限制怎么做。这是个经典问题设 f i , j f_{i,j} fi,j表示第 i i i秒在 j j j节点的方案数就可以写出转移观察到 n n n特别小 d d d特别大因此可以矩阵快速幂加速转移。
那有了 k k k怎么做呢首先可以子集反演但是容斥意义还是更简单一点的。 设 S i S_i Si表示经过 i i i节点到了第 d d d天的所有方案的集合则答案为 ∣ ⋂ S i ∣ |\bigcap S_i| ∣⋂Si∣补集相当于指定一些节点不能走也就是禁止关于它们的转移对于每个 T T T跑一次dp即可。 时间复杂度 O ( 2 k ⋅ n 3 ) O(2^k\cdot n^3) O(2k⋅n3)
后记
于是皆大欢喜。
