LOJ2409 Sum

题目链接:https://loj.ac/problem/2409
本题思想比较巧妙
直接求\(f_k\)不太可行
我们考虑从原集合随意取\(k\)个数相乘再相加
我们再去掉不是又同一个数选\(k\)个的和就可以了
我们设\(g_k\)为选出不一样的\(k\)个元素的和
比如一共三个元素
那么
\(g_1=a_1+a_2+a_3\)
\(g_2=a_1a_2+a_1a_3+a_2a_3\)
\(g_3=a_1a_2a_3\)
可以发现一些规律
\(f_1=g_1\)
\(f_2=f_1 \times g_1 -2g_2\)
\(f_3=f_2 \times g_1 – f_1 \times g_2 +3g_3\)
设几个多项式
\(F(x)=\sum f_ix^i\)
\(G(x)=\sum (-1)^{i-1}g_ix^i\)
\(H(x)=\sum (-1)^{i-1}\times i \times g_ix_i\)
那么\(F(x)=F(x)G(x)+H(x)\)
那么\(F(x)=\frac{H(x)}{1-G(x)}\)

发表评论

电子邮件地址不会被公开。 必填项已用*标注