首页 > 其他分享 >CF722F Cyclic Cipher 题解

CF722F Cyclic Cipher 题解

时间:2024-10-07 19:33:00浏览次数:8  
标签:le gcd 题解 相容 mid CF722F Cipher 序列 sim

传送门

给定 \(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\) 进行数学归纳法。

  1. \(n=2\) 显然成立。

  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

相关文章

  • [NOIP2023] 双序列拓展 题解
    qaq首先我们考虑其实这个条件就是要满足\(f\)严格比\(g\)大或\(f\)严格比\(g\)小。在这里只讨论大于。然后考虑到对于一个\(i\)如果不满足,我们可以把对应数组向右移一位看是否满足,如果还是不满足就无解了。考虑对于现在满足的\(i\),我们可以分别把两个指针向右移一......
  • EGOI2024 简单题解
    Day1T1InfiniteRace由于只有重复超过一个人才肯定是跑过一圈的,所以只用用一个数组做标记就可以了,每超过一次就打上标记,否则去掉标记。T2Bouquet定义\(dp[i]\)为,以第\(i\)种郁金香结尾的选法中最大可选的郁金香数量,易得状态转移方程为:\(dp[i]=max{dep[j]}+1(j<l_i\le......
  • mysql登录遇到ERROR 1045问题解决方法
    遇到MySQL登录时出现 ERROR1045(访问被拒绝,用户名或密码错误),可以通过以下步骤来解决:1.确认用户名和密码检查用户名和密码:确认在连接数据库时输入的用户名和密码是否正确。尝试在命令行中连接数据库,确认是否能成功登录:bash mysql-uyour_username-p2.重......
  • 题解:AT_abc374_c [ABC374C] Separated Lunch
    无耻的广告更好的阅读体验~最近在搞个人博客博客园的差点忘了更了。已经沦落到在写这种水题题解了。题目翻译有\(n\)队人,每个队人数不同,把他们分成2组(同一队的不能拆开),使两组人数差距尽量小。形式化题意:有\(n\)个数,把它们分成两组,使两组和的差尽量小。说句闲话:感觉这......
  • P3527 MET-Meteors 题解
    Solution单次二分:二分时间,做这个时间前的所有操作,然后线性统计。注意到可以整体二分,直接整体二分是\(O(n\log^2n)\)。考虑扫描序列,用线段树维护每个时间段内该位置的增加值,差分一下可以实现。将这棵线段树持久化一下,一个国家所有位置同时二分即可\(O(n\logn)\),可惜空间太......
  • P3250 网络 题解
    Solution单次二分:问“重要度\(\gex\)的所有操作,且\(t\)时间点还存在的所有操作中,是否有不经过这个点的”整体二分:保持操作、询问按时间有序,即预先按时间排序,下传时保持有序;对于一次Solve,对于所有重要度\(\gemid+1\)的操作(加入、删除),考虑与询问按时间混合排序,然后依次......
  • P3215 括号修复 题解
    Statement维护一个括号序列,有以下操作:区间覆盖区间翻转区间反转(左括号变右括号,右括号变左括号)区间问最少改多少位能使括号序列合法,保证有解Solution单纯没想到答案怎么算。。。首先一段括号序,如果消除中间的所有匹配,最终一定形如))))(((,这个信息是可合并的设这时左括......
  • P5416 = UOJ 198 时空旅行 题解
    Statement一棵树,每个节点上有一个集合,每个儿子集合由父亲集合增加一个点\((x_i,c_i)\)或删除一个点得到。根节点集合为\(\{(0,0,0,c_0)\}\)多次询问,每次问\(u\)点的集合内,\(\min\{(x_i-x)^2+c_i\}\)Solution首先你认真读完题发现原题中\(y,z\)都是没用的然后离线DFS......
  • 火星商店问题 题解
    Solution线段树套trie,秒了!\(O(n\log^2n)\)Code#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=1e5+......
  • Gym 100543G Virus synthesis 题解
    Solution首先只考虑回文串的答案;我们重点考虑的是偶回文串结论:对于偶回文串\(u\),从其最长的长度小于等于他的一半的回文后缀,或其父亲转移过来,一定是最优的证明:设\(u\)的一个回文子串为\(v\)(不是父亲),你要让\(v\tou\)的转移最优首先\(v\)不能跨过\(u\)的中点,因为此......