记录编号	30033	评测结果	AAAAAAAAAA
题目名称	[USACO Nov09] 盛大的 Farm-off	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	3.125 s
提交时间	2011-10-27 13:24:30	内存使用	23.15 MiB

#include <fstream>
#include <cstdlib>
using namespace std;

long long wei[1500001],val[1500001];

void swap(long long& a,long long& b)
{
	long long temp;
	temp=a;
	a=b;
	b=temp;
}

/*
long long mml(long long num,long long level,long long moder)
{
	long long temp=0;
	if (level>num)
		swap(num,level);
	while (level)
	{
		temp+=num;
		temp%=moder;
		level--;
	}
	return(temp);
}

long long pl(long long num,long long level,long long moder)
{
	long long temp=1;
	while (level)
	{
		temp=mml(temp,num,moder);
		level--;
	}
	return(temp);
}
*/

long long pl(long long num,long long level,long long moder)
{
	long long temp=1;
	while (level)
	{
		temp=(temp*num)%moder;
		level--;
	}
	return(temp);
}

void qqsort(long long l,long long r)
{
	long long ll,rr,temp;
	ll=l;
	rr=r;
	temp=val[(rand()%(r-l+1))+l];
	while (ll<=rr)
	{
		while (temp<val[ll])
			ll++;
		while (temp>val[rr])
			rr--;
		if (ll<=rr)
		{
			swap(val[ll],val[rr]);
			swap(wei[ll],wei[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort(l,rr);
	if (ll<r)
		qqsort(ll,r);
}

void qqsort2(long long l,long long r)
{
	long long ll,rr,temp;
	ll=l;
	rr=r;
	temp=wei[(rand()%(r-l+1))+l];
	while (ll<=rr)
	{
		while (temp>wei[ll])
			ll++;
		while (temp<wei[rr])
			rr--;
		if (ll<=rr)
		{
			swap(wei[ll],wei[rr]);
			swap(val[ll],val[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort2(l,rr);
	if (ll<r)
		qqsort2(ll,r);
}

int main(void)
{
	ifstream input("farmoff.in");
	ofstream output("farmoff.out");
	long long i,N,a,b,c,d,e,f,g,h,M,temp,temp2;
	input>>N>>a>>b>>c>>d>>e>>f>>g>>h>>M;
	temp=3*N;
	for (i=0;i<temp;i++)
	{
		wei[i]=((((a%d)*pl(i,5,d))%d+((b%d)*pl(i,2,d))%d)+c%d)%d;
		val[i]=((((e%h)*pl(i,5,h))%h+((f%h)*pl(i,3,h))%h)+g%h)%h;
	}
	qqsort(0,temp-1);
	temp2=val[N-1];
	for (i=N;i<temp;i++)
		if (val[i]!=temp2)
			break;
	if (i!=N)
		qqsort2(0,i-1);
	temp2=0;
	for (i=0;i<N;i++)
	{
		temp2+=wei[i];
		temp2%=M;
	}
	output<<temp2<<endl;
	input.close();
	output.close();
	return(0);
}