对于每一种物品构造OGF,就有: F k ( x ) = ∑ i x i v k = 1 1 − x v k F_k(x)=\sum_{i} x^{iv_k}=\frac{1}{1-x^{v_k}} Fk(x)=i∑xivk=1−xvk1 那么答案就显然是: ∏ i = 1 n F i ( x ) \prod_{i=1}^n F_i(x) i=1∏nFi(x) 转化成ln之后,加起来再exp: = exp ∑ i = 1 n ln ( F i ( x ) ) = exp ∑ i = 1 n − ln ( 1 − x v k ) \\=\exp \sum_{i=1}^n \ln(F_i(x)) \\=\exp\sum_{i=1}^n-\ln(1-x^{v_k})\\ =expi=1∑nln(Fi(x))=expi=1∑n−ln(1−xvk) 可以发现后面那个东西: ln ( 1 − x v k ) = ∫ v k x v k − 1 1 − x v k = ∫ v k x v k − 1 ∑ i = 0 x i v k = − ∑ i = 1 x i v k i \ln(1-x^{v_k})\\=\int\frac{v_k x^{v_k-1}}{1-x^{v_k}}\\=\int v_kx^{v_k-1}\sum_{i=0}x^{iv_k}\\=-\sum_{i=1}\frac{x^{iv_k}}{i} ln(1−xvk)=∫1−xvkvkxvk−1=∫vkxvk−1i=0∑xivk=−i=1∑ixivk 然后换掉上面的就可以快速算exp后面的东西了,时间复杂度 O ( n ln n ) O(n\ln n) O(nlnn) 然后做一次多项式exp即可.
