SOJ1728 题解
2024-10-21 10:06:27
题意
有一个长度为 \(n\) 的数列 \(a_0,a_1,\dots,a_{n-1}\) 以及一个长度为 \(m\) 的操作序列 \((b_0,c_0),(b_1,c_1)\dots(b_{m-1},c_{m-1})\)。
执行 \(t\) 次操作,第 \(i\) 次操作(从 \(1\) 开始编号)执行
\[\text{swap}(a_{(b_{i\bmod m}+i)\bmod n},a_{(b_{i\bmod m}+i)\bmod n})
\]
\]
求最终数列。
\(1\le n,m\le 10^5,t\le 10^{10}\)。
题解
考试题,赛时想了一个巨毒瘤的奇环树+倍增解法,结果 \(200+\) 行代码怒调 \(4\texttt{h}\),还 R 了一个点。只能 \(90\texttt{pts}\) 遗憾离场……正解用到了一个挺妙的 trick,但出题人认为很典(www被嘲讽了
先考虑 \(n\mid m\) 的情形。若我们将操作每 \(m\) 个分为一组,除最后一组外的所有组都是相同的。暴力一遍,可以得到一个置换,因为置换有结合律,用快速幂可以 \(O(n\log t)\) 解决。其实也可以优化到 \(O(n\log n)\),但没必要。
\(n\nmid m\) 时,第 \(i\) 组的每个数在 \(\bmod n\) 意义下比第 \(i-1\) 组大 \(m\)。我们这样考虑:做完第 \(1\) 组后,将数列向左循环移 \(m\) 位,做完剩下的所有组后再移回来。由于操作是 \(\texttt{swap}\),结果不变。那么除最后一组外的所有组又相同了。如上操作,最后循环右移 \(\lfloor\frac{t}{m}\rfloor\times m\) 即可。
最新文章
- JAVA for mac 的学习之路
- sysbench压力测试工具简介和使用(一)
- Xamarin.Form 实例: Discuz BBS 客户端 源码分享
- order by多个字段对索引的影响
- PostQueuedCompletionStatus
- (转)TeamCity配置笔记
- 第二章 约束和排序数据(SQL基础)
- Windows调试的基石——符号(1)
- Codeforces Round #191 (Div. 2) D. Block Tower
- php源码分析之php_info输出中css样式是怎么来的
- HTML5 移动页面自适应手机屏幕四类方法
- HighCharts之2D颜色阶梯饼图
- 芝麻HTTP: Scrapy小技巧-MySQL存储
- Beta冲刺置顶随笔
- windows下nginx代理ftp服务器
- linux服务器上部署项目,同时运行两个或多个tomcat
- Ubuntu安装mysql之后,编译找不到头文件
- MySQL索引管理及执行计划
- 单片机成长之路(51基础篇) - 009 关于sdcc的多文件编译范例(一)
- 笔记--Wcf全面解析(上)---(1)