我以前做过猎人杀但是忘记了。
题目中没有组合意义,要赋予一个。
实际上题目对一些东西求和时,其实就是猎人杀的击杀过程。
容斥一下,变成$sum_{p & 1 otin p} prod_i{frac{w[p_i]}{sum_{j=i}^{n-1}{w_j}+w_1}}$
有一个套路是猎人杀转化:(这个转化在百鸽笼里也可以使用)
这种题目可以不断的打击,直到打到一个活的人为止。
使用等比数列求和就能证明这个。
回到本题。由于和较小,所以可以枚举和。
如果设f[s]表示和为i的容斥系数
则这样子可以轻松统计答案。
用分治fft好像做不了这道题,因为要求出每一个人作为一号点的答案之和。分治fft只能求出对于一个询问的答案之和。
由于数据范围较小,f可以使用背包计算。
但是在计算的时候也不能太暴力了,要使用暴力多项式除法优化。这是个小套路。
每次由于和原来相比改动并不大,所以可以每次多项式除法,最后再乘回去。