HAOI

HAOI2019:0/?

HAOI2018:2/?

HAOI2018

奇怪的背包

请先思考后再展开

染色

请先思考后再展开

简单容斥
$$
设f_i为恰好i个颜色出现次数为ss,g_i为至少i个颜色出现次数为ss,且满足g_i=\sum_{j=i}^n C_j^if_j \\
ans=\sum_{i=0}^m w_if_i, 二项式反演得ans=\sum_{i=0}^mw_i\sum_{j=i}^m (-1)^{j-i}C_j^ig_j,那么求出g就可以fft优化卷积了 \\
g_i=C_m^iC_n^{is} \frac{(is)!}{(s!)^k} (m-k)^{n-is},O(n+mlogm)
$$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/72b2.html
转载请注明出处,谢谢!