记录编号	333575	评测结果	AAAAAAATTT
题目名称	2193.[HZOI 2015] 区间统计	最终得分	70
用户昵称	‎MistyEye	是否通过	未通过
代码语言	C++	运行时间	3.359 s
提交时间	2016-10-31 06:10:35	内存使用	103.28 MiB

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll maxn = 2000005, INF = ~0ULL>>1, mod = 1000000007;
ll N, a[maxn], A, B, C, L[maxn], R[maxn], LO[maxn], RO[maxn];
vector<ll> tong[maxn];
ll to[maxn];
int main(int argc, const char *argv[]) {
	freopen("s.in","r",stdin); freopen("s.out","w",stdout); 
	cin >>N >>a[0] >>A >>B >>C;
	A %= C, B %= C;
	for(int i=1; i<=N; ++i) a[i] = (a[i-1]*A%C+B)%C;
	for(int i=1; i<=N; ++i) tong[a[i]].push_back(i);
	int cnt = 0;
	for(int i=1; i<=C; ++i) {
		while(!tong[i].empty()) {
			to[++cnt] = i;
			a[tong[i].back()] = cnt;
			tong[i].pop_back();
		}
	}
	// for(int i=1; i<=N; ++i) printf("%lld ", a[i]); puts("");
	a[0] = a[N+1] = INF;
	for(int i=1; i<=N; ++i) {
		L[i] = i-1;
		while(a[i]>a[L[i]]) L[i] = L[L[i]];
		LO[i] = L[i]-(i!=1);
		while(a[i]>a[LO[i]]) LO[i] = L[LO[i]];
	}
	for(int i=N; i>=0; --i) {
		R[i] = i+1;
		while(a[i]>a[R[i]]) R[i] = R[R[i]];
		RO[i] = R[i]+(i!=N);
		while(a[i]>a[RO[i]]) RO[i] = R[RO[i]];
	}
	// for(int i=1; i<=N; ++i) 
	// 	printf("%lld %lld %lld %lld\n", L[i], R[i], LO[i], RO[i]);
	ll ans = 0;
	for(int i=1; i<=N; ++i) {
		// printf("0 %d\n", ans);
		++L[i], ++LO[i], --R[i], --RO[i];
		if(R[i]!=N) 
			ans += (to[a[i]])*(to[a[R[i]+1]])%mod*(i-L[i]+1)*(RO[i]-R[i])%mod;
		// printf("1 %d %d %d\n", ans, l, r);
		if(a[L[i]-1]==a[i]) continue;
		if(L[i]!=1) 
			ans += (to[a[i]])*(to[a[L[i]-1]])%mod*(L[i]-LO[i])*(R[i]-i+1)%mod;
		ans %= mod;
		// printf("2 %d %d %d\n", ans, l, r);
	}
	cout <<ans <<endl;
	getchar(), getchar();
	return 0;
}
// http://cogs.pw/cogs/problem/problem.php?pid=2193
// http://cogs.pw/cogs/problem/problem.php?pid=1917
// http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1564
// http://www.51nod.com/question/index.html#!questionId=1449