[洛谷P3784][SDOI2017]遗忘的集合

这道题挺神仙的,有一个特别奇妙的想法。
我们考虑生成函数,令$a_i=[i\in S]$
那么根据题意有(不妨令f(0)=1):
$\displaystyle\sum_{i=0}^n f(i)x^i\equiv \displaystyle\prod_{i=1}^n (\displaystyle\sum_{j=0}^{\infty } x^j)^{a_i}(\mod x^{n+1})$
又有上式右边
$\equiv \displaystyle\prod_{i=1}^n (\frac{1}{1-x^i})^{a_i}$
我们发现这个$\prod$非常地难处理,有一个骚操作就是对两边同时取对数。
左边的多项式是已知的,我们直接用多项式对数函数的求法进行求解。
我们将右边的多项式的ln直接拆开来可以得到下式:
$\displaystyle\sum_{i=1}^n a_i(\displaystyle\sum_{j=1}^{\infty} x^{ij}\frac{1}{j})$
设原式中左边取对数之后i次项系数为$b_i$,那么有:
$b_i=\displaystyle\sum_{j|i} a_j\frac{j}{i}$
$ib_i=\displaystyle\sum_{j|i} ja_j$
那么倒过来有:
$ia_i=\displaystyle\sum_{j|i} jb_j\mu(\frac{i}{j})$
所以我们只需要使用拆系数FFT实现的多项式求对数计算出所有的$b_i$,然后使用莫比乌斯函数进行计算即可。
时间复杂度$\Theta(n\lg n)$
代码:

Tagged with:

发表评论