bzoj2253 [2010 Beijing wc]纸箱堆叠

bzoj2253 [2010 Beijing wc]纸箱堆叠

​​ 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。 2<=P<=2000000000,1<=a<=p-1,a^k mod p<>0,ap<=2000000000,1<=N<=50000 HINT

Source

cdq分治+dp求最长链

三维偏序的题 注意细节 不允许有相同的 mmp 省选吃枣药丸 md简单题写了一下午

具体细节看代码

#include#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; }inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=5e4+10;struct node{ int a,b,c,d;}qr[N];int a,n,p,top,nn,s[N];inline bool cmp1(const node &a,const node &b){return a.b>1,l1,l2; while(mid>=l&&qr[mid-1].a==qr[mid].a) --mid;if (mid

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。