给定 \(n\) 个数列,第 \(i\) 个数列包含 \(k_i\) 个不超过 \(m\) 的互不相同的正整数(从 \(1\) 开始标号)。
每一秒将每个数列中的数左移一个位置(即将每个数的下标 \(-1\) , 下标 \(1\) 的数下标变为 \(k_i\)), 并记录由每个数列的第一个数组成的序列。
\(10^{100}\) 秒过后,对于所有的 \(1\leqslant x\leqslant m\) ,求 \(x\) 在记录下来的序列中出现的最长的连续的一段长度。
\(n,m\le 10^5,\sum k_i\le 2\times 10^5,k_i\le 40\)。
发现数与数之间是独立的,因此单独考虑每个数 \(x\)。称两个序列是相容的,当且仅当它们能使 \(x\) 在某个位置重合。
同时有一个小观察,如果 \(x\) 能在某个位置重合,那把序列都左移一位还是重合的,因此可以默认 \(x\) 在开头位置重合。
考虑简单情况,如果只有两个序列 \(a,b\),\(x\) 分别在 \(p_a,p_b\) 位置,怎么判断相容?
容易发现这是裴蜀定理的形式,即要存在 \(x,y\) 使得 \(ax+by=|p_a-p_b|\)。而根据裴蜀定理,有解 \(\iff\) \(gcd(a,b)\mid |p_a-p_b|\)。
求 \(gcd\) 显然是好求的,而由于每个序列内数互不相同,所以 \(p_a,p_b\) 是固定的。因此能简单判断两个序列是否相容。
然后考虑怎么判断连续一段序列是否相容?
结论:当且仅当两两相容。
证明:若一段序列都相容,显然在它们都相容的时刻可以达到两两相容。下面从两两相容证明都相容。
根据序列的个数 \(n\) 进行数学归纳法。
-
\(n=2\) 显然成立。
-
假设 \(n=k\) 时成立,则对于任意 \(n=k+1\),设 \(k+1\) 个序列长度为 \(t_1\sim t_k,p\)。由归纳法知 \(t_1\sim t_k\) 两两相容。
假设在 \(t_1\sim t_k\) 的 \(x\) 某次在 \(1\) 重合时,\(p\) 中的 \(x\) 还有 \(r\) 次才能转到 \(1\) 号位(位于 \(r+1\))。
由于两两相容,所以 \(gcd(t_i,p)\mid r\),对 \(i=1\sim k\) 均成立。设 \(q\) 为某质数,\(q\) 在 \(p\) 中幂次为 \(q_p\),在 \(r\) 中幂次为 \(q_r\),在所有 \(t_i\) 中的幂次取 \(\max\) 为 \(q_t\)。因为 \(gcd(t_i,p)\mid r\),所以 \(\min(q_p,q_t)\le q_r\),所以 \(gcd(p,lcm\{t_i\})\mid r\),所以存在 \(x,y\) 使得 \(px+lcm\{t_i\}y=r\) 的 \(x,y\),转化一下有 \(x\cdot p+r=y\cdot lcm\{t_i\}\)。这说明在所有序列左移 \(r+x\cdot p\) 之后,所有 \(x\) 都会在 \(1\) 号位。
证毕。
如何利用这个结论?显然有单调性,考虑双指针,对于每个 \(l\) 求出最大的 \(r\) 使 \([l,r]\) 相容。
因为 \(k_i\) 只有 \(40\) 种取值,相同 \(k_i\) 的序列相容当且仅当它们 \(x\) 的位置相同,因此可以记录 \(pos_i\) 表示当前区间内长度为 \(i\) 的序列的 \(x\) 在哪个位置。这样在 \(r\) 右移的时候,最多只需要判断 \(40\) 次裴蜀定理,就能确定是否相容了。
标签:le,gcd,题解,相容,mid,CF722F,Cipher,序列,sim From: https://www.cnblogs.com/FLY-lai/p/18450434