更一般的的容斥原理 对于同一固定全集
U U U 上的子集
A 1 , A 2 , … , A n ⊆ U A_1,A_2,\dots,A_n\subseteq U A 1 , A 2 , … , A n ⊆ U ，令
f : P ( U ) → G f:\mathcal P(U)\to G f : P ( U ) → G （
f f f 是一个函数，其定义域为
U U U 的所有子集，值域为
G G G ），
其中
G G G 为阿贝尔群（运算结果封闭于
G G G ，运算有结合律、交换律，每个元素有单位元、逆元）。
若满足有限可加，即： A ∩ B = ∅ ⟹ f ( A ∪ B ) = f ( A ) + f ( B ) A\cap B=\varnothing \;\Longrightarrow\; f(A\cup B)=f(A)+f(B) A ∩ B = ∅ ⟹ f ( A ∪ B ) = f ( A ) + f ( B ) 从而必有
f ( ∅ ) = 0 f(\varnothing)=0 f ( ∅ ) = 0 。
有限可加很强。其实意思就是每个
x ∈ G x \in G x ∈ G 会带个权
w x w_x w x ，一个集合
S S S 的权值
f ( S ) = ∑ x ∈ S w x f(S) = \sum_{x \in S} w_x f ( S ) = ∑ x ∈ S w x ，这就是充要的了。
为什么？因为根据定义，一个集合的权值可以拆成，两个不交且并为自身的集合之和，因此可以不断把
f ( 一个集合 ) f(一个集合) f ( 一个集合 ) 分裂成
f ( 任意一个单元素集合 ) + f ( 剩下元素组成的集合 ) f(\text{任意一个单元素集合}) + f(\text{剩下元素组成的集合}) f ( 任意一个单元素集合 ) + f ( 剩下元素组成的集合 ) 。其中
f ( 剩下元素组成的集合 ) f(\text{剩下元素组成的集合}) f ( 剩下元素组成的集合 ) 继续分拆，
f ( 任意一个单元素集合 ) f(\text{任意一个单元素集合}) f ( 任意一个单元素集合 ) 直接累计进贡献。
不难发现，贡献来自包含的每个元素，因此有限可加相当于元素带权是充要的。
则有以下三条常用的容斥恒等式： 并转交 f ( ⋃ i = 1 n A i ) = ∑ k = 1 n ( − 1 ) k + 1 ∑ 1 ≤ i 1 < i 2 < ⋯ < i k ≤ n f ( A i 1 ∩ A i 2 ∩ ⋯ ∩ A i k ) \boxed{\text{并转交}}
\qquad
f\left( \bigcup_{i=1}^n A_i \right)
= \sum_{k=1}^n (-1)^{k+1}
\sum_{1 \le i_1 < i_2 < \dots < i_k \le n}
f\left(A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}\right) 并转交 f ( i = 1 ⋃ n A i ) = k = 1 ∑ n ( − 1 ) k + 1 1 ≤ i 1 < i 2 < ⋯ < i k ≤ n ∑ f ( A i 1 ∩ A i 2 ∩ ⋯ ∩ A i k ) 交转并 f ( ⋂ i = 1 n A i ) = ∑ k = 1 n ( − 1 ) k + 1 ∑ 1 ≤ i 1 < i 2 < ⋯ < i k ≤ n f ( A i 1 ∪ A i 2 ∪ ⋯ ∪ A i k ) \boxed{\text{交转并}}
\qquad
f\left( \bigcap_{i=1}^n A_i \right)
= \sum_{k=1}^n (-1)^{k+1}
\sum_{1 \le i_1 < i_2 < \dots < i_k \le n}
f\left(A_{i_1} \cup A_{i_2} \cup \dots \cup A_{i_k}\right) 交转并 f ( i = 1 ⋂ n A i ) = k = 1 ∑ n ( − 1 ) k + 1 1 ≤ i 1 < i 2 < ⋯ < i k ≤ n ∑ f ( A i 1 ∪ A i 2 ∪ ⋯ ∪ A i k ) 交转补的交 f ( ⋂ i = 1 n A i ) = ∑ k = 0 n ( − 1 ) k ∑ 1 ≤ i 1 < i 2 < ⋯ < i k ≤ n f ( A i 1 c ∩ A i 2 c ∩ ⋯ ∩ A i k c ) \boxed{\text{交转补的交}}
\qquad
f\left( \bigcap_{i=1}^n A_i \right)
= \sum_{k=0}^n (-1)^k
\sum_{1 \le i_1 < i_2 < \dots < i_k \le n}
f\left( A_{i_1}^c \cap A_{i_2}^c \cap \dots \cap A_{i_k}^c \right) 交转补的交 f ( i = 1 ⋂ n A i ) = k = 0 ∑ n ( − 1 ) k 1 ≤ i 1 < i 2 < ⋯ < i k ≤ n ∑ f ( A i 1 c ∩ A i 2 c ∩ ⋯ ∩ A i k c ) 其中
k = 0 k=0 k = 0 的内层和按约定为
f ( U ) f(U) f ( U ) （即空交为
U U U ）。
看着不是很眼熟？把
f ( S ) f(S) f ( S ) 替换成
∣ S ∣ |S| ∣ S ∣ ，现在看懂了吗？
几乎每篇讲容斥的博客都介绍了
f ( S ) = ∣ S ∣ f(S) = |S| f ( S ) = ∣ S ∣ ，即每个元素带
1 1 1 的权（不带权）时的形式；却没几篇博客讲这么一般的形式，怎么回事呢？
沿用原题面的变量名与记号。
简要题意： 求：
( ∑ x = 1 m x [ ∃ i ∈ { 1 , 2 , … , n } : p i ∣ x ] ) m o d 376544743 \left(
\sum_{x=1}^{m}
x\,
[\, \exists \, i \in \{1, 2, \dots, n\} : p_i \mid x\,]
\right)
\bmod 376544743 ( x = 1 ∑ m x [ ∃ i ∈ { 1 , 2 , … , n } : p i ∣ x ] ) mod 376544743 其中
1 ≤ n , m 1 \leq n, m 1 ≤ n , m ，且保证满足以下条件中的其中一条：
n ≤ 20 , m ≤ 10 9 n \leq 20, m \leq 10^9 n ≤ 20 , m ≤ 1 0 9 n m ≤ 10 7 nm \leq 10^7 nm ≤ 1 0 7
思路 我做容斥的第一步，总是把符合要求的统计对象组成的集合
S S S 表示成若干个集合的交/并的结果，其中若干个要在可控的范围内。
对于这题，
S S S 即为“与给定质数集有交集的自然数”，答案即为
∑ x ∈ S x \sum_{x \in S} x ∑ x ∈ S x 。
T 1 ∪ T 2 ∪ ⋯ ∪ T n T_1 \cup T_2 \cup \dots \cup T_n T 1 ∪ T 2 ∪ ⋯ ∪ T n 记
R y R_y R y 为所有满足
1 ≤ x ≤ m 1 \leq x \leq m 1 ≤ x ≤ m 且
y ∣ x y \mid x y ∣ x 的
x x x 组成的集合，那么上式的
T i T_i T i 即为
R p i R_{p_i} R p i 。
因此我们要求的是
f ( T 1 ∪ T 2 ∪ ⋯ ∪ T n ) f(T_1 \cup T_2 \cup \dots \cup T_n) f ( T 1 ∪ T 2 ∪ ⋯ ∪ T n ) ，其中
f ( U ) = ∑ x ∈ U x f(U) = \sum_{x \in U} x f ( U ) = ∑ x ∈ U x 。
直接做肯定是不好做的，不然也不会用到容斥。我们使用第一个恒等式——并转交，那么有：
f ( ⋃ i = 1 n T i ) = ∑ k = 1 n ( − 1 ) k + 1 ∑ 1 ≤ i 1 < i 2 < ⋯ < i k ≤ n f ( T i 1 ∩ T i 2 ∩ ⋯ ∩ T i k ) .
f\left( \bigcup_{i=1}^n T_i \right)
= \sum_{k=1}^n (-1)^{k+1}
\sum_{1 \le i_1 < i_2 < \dots < i_k \le n}
f\left(T_{i_1} \cap T_{i_2} \cap \dots \cap T_{i_k}\right). f ( i = 1 ⋃ n T i ) = k = 1 ∑ n ( − 1 ) k + 1 1 ≤ i 1 < i 2 < ⋯ < i k ≤ n ∑ f ( T i 1 ∩ T i 2 ∩ ⋯ ∩ T i k ) . 其中
T i 1 ∩ T i 2 ∩ ⋯ ∩ T i k T_{i_1} \cap T_{i_2} \cap \dots \cap T_{i_k} T i 1 ∩ T i 2 ∩ ⋯ ∩ T i k 的意义即为“所有满足
1 ≤ x ≤ m 1 \leq x \leq m 1 ≤ x ≤ m 且
∀ j ∈ { 1 , 2 , … , k } , p i j ∣ x \forall \, j \in \{1, 2, \dots, k\},\, p_{i_j} \mid x ∀ j ∈ { 1 , 2 , … , k } , p i j ∣ x 的
x x x 组成的集合”，等价于
R lcm 1 ≤ j ≤ k p i j R_{\operatorname{lcm}_{1 \leq j \leq k} p_{i_j}} R lcm 1 ≤ j ≤ k p i j ；又因为保证
p i p_i p i 都是互不相同的素数，因此进一步简化为
R ∏ j = 1 k p i j R_{\prod_{j = 1}^k p_{i_j}} R ∏ j = 1 k p i j 。
f ( R y ) f(R_y) f ( R y ) 很好求，即为
y ⋅ ⌊ m y ⌋ ( ⌊ m y ⌋ + 1 ) 2 y \cdot \frac{\lfloor\frac{m}{y}\rfloor(\lfloor\frac{m}{y}\rfloor + 1)}{2} y ⋅ 2 ⌊ y m ⌋ (⌊ y m ⌋ + 1 ) ，因此可以用一个式子来表示答案：
∑ ∅ ≠ S ⊆ { 1 , … , n } ( − 1 ) ∣ S ∣ + 1 ( ∏ i ∈ S p i ) ⋅ ⌊ m ∏ i ∈ S p i ⌋ ( ⌊ m ∏ i ∈ S p i ⌋ + 1 ) 2 ( m o d 376544743 ) \sum_{\varnothing\neq S\subseteq\{1,\dots,n\}}
(-1)^{|S|+1}\left(\prod_{i\in S}p_i\right)\cdot
\frac{\left\lfloor \frac{m}{\prod_{i\in S}p_i}\right\rfloor\left(\left\lfloor \frac{m}{\prod_{i\in S}p_i}\right\rfloor+1\right)}{2}
\pmod{376544743} ∅ = S ⊆ { 1 , … , n } ∑ ( − 1 ) ∣ S ∣ + 1 ( i ∈ S ∏ p i ) ⋅ 2 ⌊ ∏ i ∈ S p i m ⌋ ( ⌊ ∏ i ∈ S p i m ⌋ + 1 ) ( mod 376544743 ) 代码 CPP #include <bits/stdc++.h>
using namespace std;
using ll = long long ;
using lll = __int128_t ;
constexpr int N = 20 , P = 376544743 ;
int p[N];
int main () sync_with_stdio (false );
cin.tie (nullptr );
int n, m;
cin >> n >> m;
for (int i = 0 ; i < n; ++i) {
cin >> p[i];
}
lll ans = 0 ;
auto dfs = [&](auto &&self, int dep, int mul, int cnt) {
if (dep == n) {
if (cnt) {
lll res = ((m / mul + 1 ) * (ll)(m / mul) >> 1 ) * (lll)mul;
ans += cnt & 1 ? res : -res;
}
return ;
}
self (self, dep + 1 , mul, cnt);
if ((ll)mul * p[dep] <= m) {
self (self, dep + 1 , mul * p[dep], cnt + 1 );
}
};
dfs (dfs, 0 , 1 , 0 );
cout << (int )(ans % P)<< '\n' ;
return 0 ;
}
实际上，有了剪枝，时间复杂度一个充分紧的上界是
Θ ( min ( 2 n , n m ) ) \Theta(\min(2^n, nm)) Θ ( min ( 2 n , nm )) ，因此不需要对两个数据范围进行分别处理。
P2429 制杖题