「JLOI2016」成绩比较-DP+拉格郎日插值法

发布于 11 天前  37 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「JLOI2016」成绩比较-DP+拉格郎日插值法

Description

太长了,咕咕咕

Solution

设\(f_{i,j}\)表示考虑前\(i\)门课程,总共有\(j\)个人被碾压的方案数。

\(f_{i,j}=\sum_{k=j}^{n-1}f_{i-1,k} \times C_{k}^{k-j} \times C^{n-R_i-1-(k-j)}_{n-k-1}\times d_i\)

\(d_i\)表示第\(i\)门功课分数合法分布的方案数,有\(d_i=\sum_{k=1}^{U_i}k^{n-R_i}(U_i-k)^{R_i-1}\)。容易发现\(d_i\)是一个次数不超过\(n\)的多项式,用插值算法求\(d_i\)即可。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「JLOI2016」成绩比较-DP+拉格郎日插值法


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前,相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!