F - Loud Cicada
题意
给你 \(n\) 个数 \(a_i\)，问有多少个 \(x \in [1,Y]\) 满足 \(a_i \mid x\) 的 \(i\) 的个数等于 \(m\)。
\(n ,m \le 20, a_i,Y \le 10^{18}\)。
思路
\(a_i \mid x\) 的 \(x\) 有 \(\lfloor \frac{Y}{a_i} \rfloor\) 个。
显然可以枚举 \(i\) 的集合，然后计算 \(\lfloor \frac{Y}{\text{lcm}(a_i ,i\in S)} \rfloor\)。
然后算容斥系数。
容斥系数可以手推出来：
设 \(f_k\) 表示 \(|S| = k\) 的容斥系数。
假设 \(m=2\)。
\(f_2 = 1\)。
\(|S|=3\) 的方案应该总共被计算 \(0\) 次，现在已经被计算了 \(\binom{3}{2}\) 次，所以 \(f_3 = - \binom{3}{2}\)。
\(|S|=4\) 的方案应该总共被计算 \(0\) 次，现在已经被计算了 \(\binom{4}{2} - \binom{3}{2} \binom{4}{3}\) 次，所以 \(f_4 = -\binom{4}{2} + \binom{3}{2} \binom{4}{3}\)。
即 \(f_m=1, f_k = - \sum_{i=m}^{k-1} \binom{k}{i} f_i\)。
于是就可以 \(O(2^n n + n^2)\) 做了。
什么广义容斥原理、什么莫比乌斯变换，我完全看不懂啊，原来的定理如何证明和怎么运用到这题都不懂，有空必须学习一下，数学实在是太差了。
注意一些爆 long long 的问题。甚至会爆 __int128。我的解决方法是计算过程对一个大质数取模，因为最终答案显然 \(< Y\)，所以是正确的吧（？。
但是亲爱的，你告诉我，只 WA 一个 01-02.txt 是什么意思？
)
