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

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 2000005;
const ll mod = 1000000007;
int N, A, B, C, L[maxn], R[maxn], LO[maxn], RO[maxn];
ll a[maxn];
#define cmp(x, y) a[x]!=a[y]?a[x]>a[y]:x>y
int main(int argc, const char *argv[]) {
	freopen("s.in","r",stdin); freopen("s.out","w",stdout); 
	cin >>N >>a[0] >>A >>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) printf("%lld ", a[i]); puts("");
	a[0] = a[N+1] = C+1;
	for(int i=1; i<=N; ++i) {
		L[i] = i-1;
		while(cmp(i, L[i])) L[i] = L[L[i]];
		LO[i] = L[i]-(i!=1);
		while(cmp(i, LO[i])) LO[i] = L[LO[i]];
	}
	for(int i=N; i>=0; --i) {
		R[i] = i+1;
		while(cmp(i, R[i])) R[i] = R[R[i]];
		RO[i] = R[i]+(i!=N);
		while(cmp(i, 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 += a[i]*a[R[i]+1]%mod*(i-L[i]+1)%mod*(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 += a[i]*a[L[i]-1]%mod*(L[i]-LO[i])%mod*(R[i]-i+1)%mod;
		ans %= mod;
		// printf("2 %d %d %d\n", ans, l, r);
	}
	cout <<ans <<endl;
	getchar(), getchar();
	return 0;
}