183 E

题目最难点就是前面的区间离散 如果能想到这个这道题就不难了 把所有的l[i] r[i] 放在一起然后排序 考虑一个区间 先把所有可能取到这个区间的点取出来 计算出这些点在这个区间内 区间左 区间右的概率 记为 pl pm pr 那么一个点在这个区间内 他排名的的概率可以这么计算 f[i][x][y] 前i个i点 在这个区间内有x个点 区间前面有y个点 转移就是第i个点加进来 考虑是在左边 中间 还是右边 f[i][j][k]+=f[i-1][j-1][k]*pl[i]; f[i][j][k]+=f[i-1][j][k-1]*pm[i]; f[i][j][k]+=f[i-1][j][k]*pr[i]; 注意到如果在同一个区间内有k个人 那么期中任意一个人排1-k名的概率是一样的 所以可以这么 统计答案： for (int x=0;x<m;x++) for (int y=0;y<m-x;y++) for (int k=0;k<=y;k++) rec[id[p]][cnt+x+k+1]+=pm[p]*f[m-1][x][y]/(y+1);

直接裸做DP的话 效率是 n^5 好像是堪堪过 可以看到在同一个区间里面计算不同点的 f[i][x][y] 时 他们之间有很大一部分的dp过程是一模一样的 所以肯定还是可以优化的 （一开始我想的是 f[i][x][y]表示从1到i的 t[i][x][y] 表示i到m的 然后计算的时候从f[i-1] t[i+1]得到答案 但是算了算 是N^6 比暴力还差。。。囧，这样二元的多项式函数乘积如果可以FFT也许也行，不过二元FFT 想想也就呵呵了） 后来看到了CLJ的代码 他是分治搞的 ORZ 代码也容易理解 这里就不说了 分治的话 就是N^4logN

懒得敲分治了 直接就写暴力了