#P2253. [2010 Beijing wc]纸箱堆叠

    ID: 1284 传统题 3000ms 256MiB 尝试: 741 已通过: 165 难度: 7 上传者: 标签>CF2200提高+/省选-DAG 动态规划CDQ 分治树状数组离散化稀疏状态重置

[2010 Beijing wc]纸箱堆叠

题目描述

PP 工厂是一个生产纸箱的工厂。纸箱生产线在人工输入三个参数 n,p,an,p,a 之后,即可自动化生产三边边长为:

(a mod pa \bmod p,a2 mod pa^2 \bmod p,a3 mod pa^3 \bmod p) (a4 mod pa^4 \bmod p,a5 mod pa^5 \bmod p,a6 mod pa^6 \bmod p) ⋯\cdots (a3n−2 mod pa^{3n-2} \bmod p,a3n−1 mod pa^{3n-1} \bmod p,a3n mod pa^{3n} \bmod p)

的 nn 个纸箱。在运输这些纸箱时,为了节约空间,必须将它们嵌套堆叠起来。一个纸箱可以嵌套堆叠进另一个纸箱当且仅当它的最短边、次短边和最长边长度分别严格小于另一个纸箱的最短边、次短边和最长边长度。这里不考虑任何旋转后在对角线方向的嵌套堆叠。

你的任务是找出这 nn 个纸箱中数量最多的一个子集,使得它们两两之间都可嵌套堆叠起来。

输入格式

输入文件的第一行三个整数,分别代表 a,p,na,p,n。

输出格式

输出文件仅包含一个整数,代表数量最多的可嵌套堆叠起来的纸箱的个数。

10 17 4
2

样例说明 1

生产出的纸箱的三边长为(10,15,1410,15,14),(4,6,94,6,9),(5,16,75,16,7),(2,3,132,3,13)。其中只有(4,6,94,6,9)可堆叠进。

(5,16,75,16,7),故答案为 22。

数据规模与约定

100%100\% 的数据满足:2≤p≤2×1092 \le p \le 2 \times 10^9,1≤a≤p−11 \le a \le p-1,ak mod p>0a^k \bmod p > 0,a⋅p≤2×109a \cdot p \le 2 \times 10^9,1≤n≤5×1041 \le n \le 5 \times 10^4。