如何用集合划分容斥找出[ABC236Ex]的互不相同倍数？
摘要：$text{Solution}$ 关键限制是 $2.A_inot= A_j$ 这也是上午模拟赛 $T3$ 导致我暴力不会的东西 考虑更一般的，连边 $(i,j)$，表示 $a_i=a_j$ 的限制，那么本题考虑这样的一个完全图 那么枚举
\(\text{Solution}\)
关键限制是 \(2.A_i\not= A_j\)
这也是上午模拟赛 \(T3\) 导致我暴力不会的东西
考虑更一般的，连边 \((i,j)\)，表示 \(a_i=a_j\) 的限制，那么本题考虑这样的一个完全图
那么枚举选哪些边，记为集合 \(S\)，于是答案就是 \(\sum_S (-1)^{|S|}f(S)\)
\(f(S)\) 此时的计算就面临一些连通块，连通块内要求 \(a\) 相等，这是容易计算的
但容斥本身是 \(O(2^m)\)，考虑优化
因为枚举选的边集，很多 \(f(S)\) 是相同的，因为计算只取决于各个连通块的情况，而完全图一些边的差异不会影响各个连通块的连通关系，那么优化 \(f(S)\) 的定义，转向只考虑点集，\(f(S)\) 表示将点集 \(S\) 划分成若干个连通的答案
那么 \(f(S)\) 就是各个连通块方案数带容斥系数的和
考虑一个连通块的答案 \(g(S)\)，一开始连通块的限制也是个完全图
那么继续枚举边集，要求选了的边集能使点集 \(S\) 连通
\(g(S)=\sum_E (-1)^{|E|}F(S)\)，\(F(S)\) 表示连通块 \(S\) 内要求 \(a\) 都相同的答案，这是容易计算的
记容斥系数和为 \(h(S)\)，算 \(h(S)\) 的话连通约束较困难，再容斥计算，记 \(n=|S|\)
不考虑连通，那么直接枚举选了几条边即可，可以看出是个二项式定理，那么有答案为 \([n=1]\)
再减掉不连通的情况，此时 \(S\) 被分成若干连通块，为避免考虑连通块时算重，枚举代表元所在连通块大小
那么 \(h(n)=[n=1]-\sum_{i=1}^{n-1}\binom{n-1}{i-1}h(i)[n-i=1]\)，得到 \(h(n)=(-1)^{n-1}(n-1)!\)
原来这是一个经典的容斥模型，即集合划分容斥。
本题 \(f(S)\) 的转移是枚举子集的，但仍会算重，同样枚举代表元所在连通块
\(\text{Code}\)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 17, P = 998244353;
int n, h[N], f[1 << N], g[1 << N], num[1 << N];
LL m, d[N];
void Add(int &x, int y){((x += y) >= P) && (x -= P);}
int main() {
scanf("%d%lld", &n, &m);
for(int i = 0; i < n; i++) scanf("%lld", &d[i]);
h[1] = 1;
for(int i = 2; i <= n; i++) h[i] = (P - (LL)(i - 1) * h[i - 1] % P) % P;
int all = (1 << n) - 1;
for(int i = 1; i <= all; i++) {
for(int j = i; j; j -= j & -j) ++num[i];
LL lcm = 1;
for(int j = 0; j < n; j++) if (i >> j & 1) {
lcm /= __gcd(lcm, d[j]);
if (lcm > m / d[j]) {lcm = m + 1; break;}
lcm *= d[j];
}
g[i] = m / lcm % P;
}
f[0] = 1;
for(int s = 1; s <= all; s++) {
int now = __builtin_ctz(s);
for(int t = s; t; t = (t - 1) & s) if (t >> now & 1)
Add(f[s], (LL)g[t] * h[num[t]] % P * f[s ^ t] % P);
}
printf("%d\n", f[all]);
}