[USACO Nov09]盛大的 Farm-off

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 farmoff.in 输出文件 farmoff.out

问题描述:

    农夫约翰拥有 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