CF1043F - Make It One

考虑加入一个数如果不能使公因数减少,则可以不放。计算可得答案必定 $\leq 7$。又发现不能直接对存在性进行容斥,容斥方案数即可。

($cnt_i$ 表示以 $i$ 为因数的数的个数,$f_i$ 表示选 $ans$ 个数使得公因数为 $i$ 的方案数。)

AT2064 - Many Easy Problems

容斥可得:

$$
ans_k = n {n \choose k} - \sum\limits_{u=1}^n ({n - siz_u\choose k} + \sum\limits_{v \in son_u} {siz_v \choose k})
$$

NTT 一波即可。

同理可 Min-Max 容斥:

$$
\min(S) = \frac{1}{1 - \sum\limits_{S’ \subseteq S} \sum\limits_{u \in S’} p_u}
$$

FWT 一波即可。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×