记录编号	423555	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[郑州集训 2017]NOI模拟题5.1	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	7.619 s
提交时间	2017-07-12 08:46:15	内存使用	38.46 MiB

#include <cstdio>
#include <iostream>
#include <algorithm>
// DATA_GEN --- BEGIN ---// 你可以直接将这个数据生成器嵌入到你的代码中
// 或者，你也可以根据自己程序的需要，自己改写这个数据生成器
// 使用方法：从输入文件读入 N 和随机数种子之后，调用 gen_data 方法，可以将获得的排列 {A}, {B}, {C} 分别存放在对应 3 个数组中
const int MAXN = 2e6 + 10;
int lastInt, seed;
inline int nextInt() {
	static const int mod = 1e9 + 7;
	lastInt = lastInt ^ (((long long) lastInt * lastInt + seed) % mod);
	return lastInt;
}
void getPerm(int P[], int n, int x0, int c) {
	for (int i = 1; i <= n; ++i) P[i] = i;
	lastInt = x0;
	seed = c;
	for (int i = n; i >= 1; --i) std::swap(P[i], P[nextInt() % i + 1]);
}
int n, A[MAXN], B[MAXN], C[MAXN];  // 生成的排列将存储在这三个数组中
void gen_data(int n, int a0, int seed_a, int b0, int seed_b, int c0, int seed_c) {
	getPerm(A, n, a0, seed_a);
	getPerm(B, n, b0, seed_b);
	getPerm(C, n, c0, seed_c);
}
// DATA_GEN --- END ---
typedef long long ll;
ll ans;
struct bit{
	int a[MAXN];
	void add(int p,int d){
		for (;p<=n;p+=p&-p) a[p]+=d;
	}
	int sum(int p){
		int ans=0;
		for (;p;p-=p&-p) ans+=a[p];
		return ans;
	}
}T;
int q[MAXN];
ll calc(int *A,int *B){
	ll ans=0;
	for (int i=1;i<=n;i++) q[A[i]]=i;
	for (int i=1;i<=n;i++) T.a[i]=0;
	//for (int i=1;i<=n;i++) printf("(%d,%d)\n",A[q[i]],B[q[i]]);
	for (int i=1;i<=n;i++) ans+=T.sum(B[q[i]]),T.add(B[q[i]],1);
	//printf("ans=%lld\n",ans);
	return ans;
}
int main()
{
	freopen("order1.in", "r", stdin);
	freopen("order1.out", "w", stdout);
	int a0, s_a;
	int b0, s_b;
	int c0, s_c;
	std::cin >> n;
	std::cin >> a0 >> s_a;
	std::cin >> b0 >> s_b;
	std::cin >> c0 >> s_c;
	gen_data(n, a0, s_a, b0, s_b, c0, s_c);
	ans=-1ll*n*(n-1)/2;
	ans+=calc(A,B);
	ans+=calc(B,C);
	ans+=calc(A,C);
	printf("%lld\n",ans/2);
	fclose(stdin);
	fclose(stdout);
	return 0;
}