我们要求的是
[sum_{k=0}^n f(k) imes x^k imes inom{n}{k}
]
把普通多项式 (f(k)=sum_{i=0}^m a_ik^i)转换成下降幂多项式(g(k)=sum_{i=0}^m b_ik^{underline{i}})
那么原式就是 :
[sum_{k=0}^n sum_{i=0}^m b_ik^{underline{i}} imes x^k imes inom{n}{k}
]
有一个性质是 :
[inom{n}{k} imes k^{underline{i}} = inom{n-i}{k-i} imes n^{underline{i}}
]
于是原式变成 :
[sum_{k=0}^n sum_{i=0}^m b_i imes x^k imes inom{n-i}{k-i} imes n^{underline{i}}
]
把(b_i)提到前面 :
[sum_{i=0}^m b_i sum_{k=0}^n x^k imes inom{n-i}{k-i} imes n^{underline{i}}
]
(i>k)时后面的为0,所以枚举(k)可以转化为枚举(k-i),就相当于:
[sum_{i=0}^m b_i sum_{k=0}^{n-i} x^{k+i} imes inom{n-i}{k} imes n^{underline{i}}
]
整理系数得 :
[sum_{i=0}^m b_ix^in^{underline{i}} sum_{k=0}^{n-i} x^k imes inom{n-i}{k}
]
发现后面添上1是二项式定理的展开(同subtask 4~8 (m=0)),式子变成 :
[sum_{i=0}^m b_ix^in^{underline{i}} (x+1)^{n-i}
]
现在问题在于求(b_i),就是普通多项式转下降幂多项式。
因为(x^k = sum_{i=0}^k x^{underline{i}} imes S2(k,i)),(S2)表示第二类斯特林数。
所以 :
[sum_{i=0}^m a_ik^i = sum_{i=0}^m a_i sum_{j=0}^i k^{underline{j}} imes S2(i,j)
]
相当于 :
[sum_{i=0}^m k^{underline{i}} sum_{j=i}^m a_j imes S2(j,i)
]
那么 :
[b_i=sum_{j=i}^m a_j imes S2(j,i)
]
可以(O(m^2))预处理(b_i),然后代回原式(O(m))计算。