●BZOJ 4559 [JLoi2016]成绩比较

题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=4559

题解：

计数dp，拉格朗日插值法。
真的是神题啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。先来看看 dp定义：(由于每门课程的分数分布方案是独立的，所以先不管每科实际分数大小所贡献的方案数。)
dp[i][j]:表示前 i门课程，只考虑分数相对大小关系时，B神碾压了 j个人的方法数
也就是说上面的dp定义只是表示一个相对关系的方案数(即不考虑实际分数大小)。
那么dp的转移：
dp[i][k] += dp[i-1][j]*C(j,k)*C(N-j,N-R[i]-k)
含义呢：就是从在前i-1门课程中被碾压的 j 名同学中选出 k 个来继续碾压(即让他们该科分数任比B神低)；同时在没有被碾压的 N-j个同学中选出N-R[i]-k个来使得他们的该科分数任比B神低。(使B神排在该门课程的第 R[i]名)

如果设 Y[i]表示第i门课程且B神排在第R[i]名时的分数分布方案数。

则

最后的答案就是 dp[N][k]*Y[1]*Y[2]*Y[3]*...*Y[M]

但是求这个 Y[i]就有点麻烦了，里面的 U[i]很大呀，根本不能跑循环去求和。
然后就要用到插值法了。 (不懂插值法？快点击这里，简单入门一波，很快的 ~)
再明确一下当前的目标: 某一门课程，总分为 U，B神排名为 R，求分数分布方案数。
令插值函数

则答案即为 P[U]。
不难发现，求和式的每一项的都不超过 X^(N-1),同时又最多只有 X项相加，
所以 P[X] 是最高次项的次数不超过 N 的多项式。
那么求出这个多项式，就只需要 N+1个点，就用插值法求出该函数了。
所以O(N^2*logN(快速幂的log))的复杂度暴力求出前 N+1个点的函数值
(X₁=1,P[1]) , (X₂=2,P[2]) ...... (X_N+1=N+1,P[N+1])
然后插值法得到函数 P[X]。
然后再 O(N^2)的复杂度求出 X=U 时的函数值 P[U],即可得到当前科目的分数分布方案:Y[当前科目]。
又因为有 M 门科目，所以求 Y[]数组的总复杂度为 O(N^3*logN)
erge的插值法代码：

ll Lagrange(ll U,ll R)
{
	static ll p[MAXN];
    for(int i=1;i<=n+1;i++){
        p[i]=0;
        for(int j=1;j<=i;j++)
            p[i]=(p[i]+Pow(j,n-R)*Pow(U-j,R-1))%Mod;
    }
    ll ret=0;
    for(int i=1;i<=n+1;i++){
        ll mul=1;
        for(int j=1;j<=n+1;j++)if(j!=i)
            mul=mul*(U-j+Mod)%Mod*inv[i-j+500]%Mod;
        mul=mul*p[i]%Mod;
        ret=(ret+mul)%Mod;
    }
    return (ret+Mod)%Mod;
}