有空就写,随机更新
P4389 付公主的背包
由生成函数含义易得答案为
\[\prod_{i=1}^{n}{\frac{1}{1-x^{v_i}}}
\]
正常算需要 \(O(nm\log m)\) 考虑优化
乘法不好算，通过求 \(\ln\) 改为加法，设
\[A(x)=\prod_{i=1}^{n}{\frac{1}{1-x^{v_i}}}
\]
显然有
\[\begin{split}
A(x)&=exp(\ln(\ A(x)\ ))\\
&=exp(\sum_{i=1}^{n}{\ln(\frac{1}{1-x^{v_i}}}))
\end{split}
\]
求和非常好做，接下来只需要快速求出\(\frac{1}{1-x^{v_i}}\)就行了，我们有:
\[\]
证明:
设:
\[F(x)=\frac{1}{1-x^v}\\
\ln F(x)=\ln(\frac{1}{1-x^v})=-\ln (1-x^v)
\]
求导(链式法则)
\[(\ln F(x) )^{\prime}=(-\ln (1-x^v) )^{\prime}=-\frac{(1-x^v)^{\prime}}{(1-x^v)}
\]
因为 \((1-x^v)^{\prime}=-vx^{v-1}\) 所以
\[(\ln F(x) )^{\prime}=\frac{vx^{v-1}}{(1-x^v)}
\]
把下面的 \(\frac{1}{1-x^v}\) 带成 \(\sum_{i=0}^{\infty}{x^{i\times v}}\)
\[(\ln F(x) )^{\prime}=vx^{v-1}\sum_{i=0}^{\infty}{x^{i\times v}}=v\sum_{i=0}^{\infty}{x^{i\times v+v-1}}=v\sum_{i=0}^{\infty}{x^{v\times(i+1)-1}}
\]
积分回去
\[\ln F(x)=v \sum _ {i=0}^{\infty}{\frac{x^{v\times(i+1)}}{i\times v+v}}
\]
约分
\[\ln F(x)=\sum _ {i=0}^{\infty}{\frac{x^{v\times(i+1)}}{i+1}}
\]
更改枚举指标
\[\ln F(x)=\sum_ {i=1} ^{\infty} {\frac{x^{v \ i}}{i}}
\]
带回原式算答案即可