590. [USACO Nov09] 盛大的 Farm-off

问题描述:

    农夫约翰拥有 3*N(1 <= N <= 500,000)只牛，它们的编号为0..3*N-1，每只牛都有一个体重 W_i(1 <= W_i <= d)。约翰参加了一个叫做 Farm-off 的盛大竞赛活动，在这个活动上他可以在整个农业界炫耀他的牛。
    这个竞赛约翰可以派出一队共 N 头牛参赛，他的每头牛都有一个效率值 U_i (1 <= U_i <= h)，这个值用来描述他认为在这个竞赛中每头牛的有用值。约翰想让他选择的一群牛有一个最大的效率总值。
    可能有很多种 N 头牛的集合可以达到这个最大的效率总值。农夫约翰为了防止竞赛中的欺骗行为，对牛的体重加以限制。所以第二个要考虑的因素便是参加竞赛的牛的体重。
    帮助约翰从所有以N头牛组合而得的效率总值最大的集合中，找到一个最小体重的组合。 并且打印出体重总值被M (10,000,000 <= M <= 1,000,000,000)整除后的余数。
    注意：为了尽快地输入，约翰找到一个能够表示出每头牛体重及效率值的多项式：
对于每头牛   0 <= i < 3*N，
            W_i = (a*i^5+b*i^2+c) mod d
            U_i = (e*i^5+f*i^3+g) mod h
合理的系数范围：
0 <= a <= 1,000,000,000;
0 <= b <= 1,000,000,000;
0 <= c <= 1,000,000,000;
0 <= e <= 1,000,000,000;
0 <= f <= 1,000,000,000;
0 <= g <= 1,000,000,000;
10,000,000 <= d <= 1,000,000,000;
10,000,000 <= h <= 1,000,000,000.
公式有时会产生一些重复的数字，你的算法应该能够适应这种情况。

 PROBLEM NAME: farmoff

输入格式：
第一行：用空格隔开的10个数字：N, a, b, c, d, e, f, g, h,M
输入样例：(file farmoff.in):
 2 0 1 5 55555555 0 1 0 55555555 55555555
根据公式计算出来的 W_i 分别是：5, 6, 9, 14, 21,30；计算出来的U_i分别是：0, 1, 8, 27, 64,125
输出格式：
第一行：一个单独的整数用来描述：N头牛的净效率总值最大的条件下的最小体重总值。
输出样例（farmoff.out）：
51
两只牛的组合中效率最大的是牛5和牛6，它们的体重总值为：21+30=51