题目来源: 2019 ICPC Asia EC Final: H. King
题目来源: XJTUOJ-1223 zxh的一气通贯
题目链接: https://oj.xjtuicpc.com/problem/1223
题面
一共 \(T\) 组数据.
给定素数 \(p\), 以及长度为 \(n\) 的序列 \(a_1,a_2,\cdots, a_n\).
需要找出满足下列条件的子序列 \(b_1,b_2,\cdots,b_m\) 的最大长度:
- 子序列长度 \(m\ge n/2\).
- \(\forall i\in[1,m)\cap\mathbb N\), \(\exists q\in\mathbb N\), s.t. \(qb_i\equiv b_{i+1}\pmod p\). 即子序列在模 \(p\) 意义下是等比子序列.
若不存在这种子序列, 输出 -1
.
数据范围
\[ 1\le T<1000 \]
\[ 1\le n\le2\times10^5 \]
\[ 2\le p\le10^9+7 \]
\[ 1\le a_1,a_2,\cdots,a_n<p \]
保证输入的 \(p\) 是素数. 数据组中 \(n\) 的总和不超过 \(2\times10^5\).
阅读全文…