Description
P 工厂是一个生产纸箱的工厂。纸箱生产线在人工输入三个参数 n p a , 之后，即可自动化生产三边边长为
(a mod P,a^2 mod p,a^3 mod P)
(a^4 mod p,a^5 mod p,a^6 mod P)
....
(a^(3n-2) mod p,a^(3n-1) mod p,a^(3n) mod p)
的n个纸箱。在运输这些纸箱时，为了节约空间，必须将它们嵌套堆叠起来。一个纸箱可以嵌套堆叠进另一个纸箱当且仅当它的最短边、次短边和最长边
长度分别严格小于另一个纸箱的最短边、次短边和最长边长度。这里不考虑任何旋转后在对角线方向的嵌套堆叠。
你的任务是找出这n个纸箱中数量最多的一个子集，使得它们两两之间都可嵌套堆叠起来。
Input
输入文件的第一行三个整数，分别代表 a,p,n
Output
输出文件仅包含一个整数，代表数量最多的可嵌套堆叠起来的纸箱的个数。
Sample Input
10 17 4
Sample Output
2
【样例说明】
生产出的纸箱的三边长为(10, 15, 14), (4, 6, 9)
, (5, 16, 7), (2, 3, 13)。其中只有(4, 6, 9)可堆叠进(5, 16, 7)，故答案为 2。
Hint
2<=P<=2000000000,1<=a<=p-1,a^k
mod p<>0,ap<=2000000000,1<=N<=50000
这题挺难的。
下面是老师给我的题解：
看这题有点像个3维的偏序问题，但并不完全是，题目要求的是最大的类似于套娃的东西。
我们先按最短边排序，然后对于一个i，只有可能是j（1<=j<i）这个纸箱可以被i包含，我们记录f[i]表示i这个箱子可以包含多少个玩具。则很显然我们可以枚举这个j（1<=j<i）如果j被i完全包含，则f[i] = max(f[i], f[j] +１)，最后在ｆ数组中取最大值就是答案。
这个ＤＰ是Ｏ（ｎ＾２）级别的，我们考虑怎么优化。
方法一：
考虑到我们在排序后未知的有２维，我们可以用树套树来实现，树套树代码短，简单无脑，但是速度非常慢，即使用最快的树状数组套线段树，最慢的点要跑到0.75ms。
方法二：
用分治来优化这个DP，还是先按x排序，然后对于一个区间L,R，记mid为区间中点，我们先递归处理（L,mid），然后考虑（L，mid）对（mid+1，r）的影响，因为我们已经保证x单调递增，然后我们保证前一段区间和后一段区间的y是单调递增的，然后我们就可以用1个指针w，并枚举i（mid+1<=i<=r）,我们要保证w之前的y小于i之前的y，然后每次把w往后移，同时插入z坐标，对于枚举到的i，用一个数状数组查询之前的最大值。最后递归（mid+1, r）。
我参考了dalao的博客。
传送门：http://blog.csdn.net/v5zsq/article/details/51083312
program box(input,output);
var
a,x,y,z,f,b,c,d:array[..]of longint;
h:array[..]of longint;
m,p,n,i,j,t,l,r,mid,ans,cnt:longint;
flag:boolean;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure sort0(q,h:longint);
var
i,j,c,t:longint;
begin
i:=q;j:=h;c:=x[(i+j)>>];
repeat
while x[i]<c do inc(i);
while c<x[j] do dec(j);
if i<=j then
begin
t:=x[i];x[i]:=x[j];x[j]:=t;
t:=y[i];y[i]:=y[j];y[j]:=t;
t:=z[i];z[i]:=z[j];z[j]:=t;
inc(i);dec(j);
end;
until i>j;
if j>q then sort0(q,j);
if i<h then sort0(i,h);
end;
procedure sorta(q,h:longint);
var
i,j,x,t:longint;
begin
i:=q;j:=h;x:=a[(i+j)>>];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if i<=j then
begin
t:=a[i];a[i]:=a[j];a[j]:=t;
inc(i);dec(j);
end;
until i>j;
if j>q then sorta(q,j);
if i<h then sorta(i,h);
end;
function find(x:longint):longint;
begin
l:=;r:=m;
while l<r- do
begin
mid:=(l+r)>>;
if a[mid]<x then l:=mid+ else r:=mid;
end;
if a[l]=x then exit(l) else exit(r);
end;
procedure sort(q,h:longint);
var
i,j,x,t:longint;
begin
i:=q;j:=h;x:=b[(i+j)>>];
repeat
while b[i]<x do inc(i);
while x<b[j] do dec(j);
if i<=j then
begin
t:=b[i];b[i]:=b[j];b[j]:=t;
t:=c[i];c[i]:=c[j];c[j]:=t;
t:=d[i];d[i]:=d[j];d[j]:=t;
inc(i);dec(j);
end;
until i>j;
if j>q then sort(q,j);
if i<h then sort(i,h);
end;
procedure change(k,n:longint);
begin
while k<=m do
begin
if n>a[k] then begin a[k]:=n;inc(cnt);h[cnt]:=k; end else break;
k:=k+k and (-k);
end;
end;
function ask(k:longint):longint;
var
ans:longint;
begin
ans:=;
while k> do begin ans:=max(ans,a[k]);k:=k-k and (-k); end;
exit(ans);
end;
procedure solve(l,r:longint);
var
mid:longint;
begin
if l=r then exit;
flag:=false;
for i:=l+ to r do if x[i]<>x[i-] then begin flag:=true;break; end;
if not flag then exit;
mid:=(l+r)>>;
i:=mid;j:=mid;if (r-l) mod = then inc(j);
if x[i]<>x[j] then mid:=i
else
while true do
begin
dec(i);inc(j);
if x[i]<>x[i+] then begin mid:=i;break; end;
if x[j]<>x[j-] then begin mid:=j-;break; end;
end;
solve(l,mid);
for i:=l to r do begin b[i]:=y[i];c[i]:=z[i];d[i]:=i; end;
sort(l,mid);sort(mid+,r);
i:=l;j:=mid+;cnt:=;
while true do
begin
if j>r then break;
if (i<=mid) and (b[i]<b[j]) then begin change(c[i],f[d[i]]);inc(i); end
else begin f[d[j]]:=max(f[d[j]],ask(c[j]-)+);inc(j); end;
end;
for i:= to cnt do a[h[i]]:=;
solve(mid+,r);
end;
begin
assign(input,'box.in');assign(output,'box.out');reset(input);rewrite(output);
readln(m,p,n);
j:=;
for i:= to n do
begin
j:=j*m mod p;x[i]:=j;
j:=j*m mod p;y[i]:=j;
j:=j*m mod p;z[i]:=j;
if x[i]>y[i] then begin t:=x[i];x[i]:=y[i];y[i]:=t; end;
if x[i]>z[i] then begin t:=x[i];x[i]:=z[i];z[i]:=t; end;
if y[i]>z[i] then begin t:=y[i];y[i]:=z[i];z[i]:=t; end;
end;
sort0(,n);
for i:= to n do a[i]:=z[i];
sorta(,n);
m:=;
for i:= to n do if a[i]<>a[i-] then begin inc(m);a[m]:=a[i]; end;
for i:= to n do z[i]:=find(z[i]);
for i:= to n do f[i]:=;
fillchar(a,sizeof(a),);
solve(,n);
ans:=;
for i:= to n do if f[i]>ans then ans:=f[i];
write(ans);
close(input);close(output);
end.