首页 > 其他分享 >P4156 论战捆竹竿 题解

P4156 论战捆竹竿 题解

时间:2024-11-09 18:07:47浏览次数:4  
标签:12 15 题解 bmod 论战 P4156 new 短路 等差数列

论战捆竹竿

题意:给定字符串 \(s\),计数 "串 \(t\) 的长度" 可能的种数有多少种,使得 \(t\) 能被 \(s\) 作为印章印出来,且 \(|t|\le w\)。\(n=|s|\le 5\times 10^5\),\(n\le w\le 10^{18}\)。

第一步:
求出 \(s\) 的周期 \(\{a_1\sim a_m\}\),包含 \(n\)(\(a_m=n\))。转化为求 \(\sum a_ib_i\le w-n\) 的情况下,\(\sum a_ib_i\) 的取值有多少种,要求 \(b_i\ge 0\)。记 \(w_0=w-n\)。

第二步:
\(\sum a_ib_i\) 的形式,考虑同余最短路。(当题目中出现类似 "若干个数求和" 的形式,可以考虑同余最短路
记 \(A=\min a_i\),令 \(F_i\) 表示 \(\bmod A=i\) 的所有数中,能表示为 \(\sum a_ib_i\) 的最小数是多少。
如果这里直接跑最短路,一共有 \(A\) 个点,每个点通过 \(a_1\sim a_m\) 都会连出 \(m\) 条边,所以复杂度至少是 \(O(A\cdot m)\) 的。同时可以构造出来 \(s=aaa\dots abaa\dots aaa\),使得周期数量达到 \(O(n)\) 个,同时周期的长度都是 \(\ge n/2\) 的,肯定能被卡。

第三步:
我们需要改进这个方法。根据 border 理论,\(\{a_1\sim a_m\}\) 可以被分成 \(\log n\) 个等差数列。
把每个等差数列单独拎出来,依次考虑。

考虑第 \(k\) 个等差数列 \(\{x,x+d,x+2d,\cdots,x+td\}\),构造 \(x\) 个点编号 \(0\sim x-1\)。\(F(i)\) 表示如果使用前 \(k-1\) 个等差数列中的数,它们能组成的数中,\(\bmod x=i\) 的最小数是多少。
我们要用 \(F(i)\) 推出 \(F_{new}(i)\):使用前 \(k\) 个等差数列中的数,它们能组成的数中,\(\bmod x=i\) 的最小数是多少。

首先把同余最短路的图建出来。观察发现,按照 \(gcd(x,d)\) 分类,每一类之间没有边,内部有边。于是我们把 \(\bmod gcd(x,d)\) 相等的一起处理。
也就是说,比如 \(gcd(x,d)=3\),先把 \(F(0),F(3),F(6),\dots\) 转移到 \(F_{new}(0),F_{new}(3),\dots\),然后再转移 \(F(1),F(4),\dots\) 和 \(F(2),F(5),\dots\),各自求解,然后拼出来 \(F_{new}\)。

如果还是把 \(\bmod gcd(x,d)\) 相等的点拿出来跑最短路,还是没有优化。这里有一个破环为链的 DP 想法。举个例子,比如当前等差数列是 \(\{15,24,33\}\),\(gcd(15,9)=3\),所以按 \(3\) 的余数分类。比如现在正在处理 \(F(1,4,7,10,13)\)。它们之间的边连出来应该是这样:

不妨 \(F(10)\) 是其中最小的点。我们以 \(10\) 这个点破环为链:只保留从前往后的边(不越界)。我们会证明,在这个链图上如果跑最短路,答案和环图是一样的。

证明:考虑到点 \(x\) 的最短路,假设破环为链的起点是 \(st\)。如果存在另一个点 \(y\),走了一条不存在的边使得 \(dist[x]\) 更短了。但是因为 \(st\) 是 \(F()\) 最小的,所以 \(F(st)<F(y)\);同时因为 \(y\) 走到 \(x\) 是越界的,所以 \(y\) 到 \(x\) 一定比 \(st\) 到 \(x\) 更远,根据等差数列的性质,\(st\) 一定存在一条比 \(y\rightarrow x\) 的边更短的。因为 \(F(st)<F(y)\),而且 \(st\) 出发还有更小的边,所以一定不会存在这样的 \(y\)。

因此我们只需要保留这个链图跑最短路。但是真的需要跑最短路吗?是可以优化的。
记链上第 \(i\) 个点的 \(F_{new}\) 值为 \(g_i\)(从 \(0\) 开始编号)。首先可以写出一个朴素的 DP 方程。

\(g_i=\min\{F(i),g[j]+x+(i-j)d|i-t\le j\le i-1,j\ge 0\}\)。这里 \(i-t\) 的 \(t\) 是上面 \(x+td\) 的 \(t\)。

这个式子很显然可以单调队列优化,于是复杂度从最短路和边数有关的复杂度,降低到 \(O(\text{点数})\)。

这一部分贡献的复杂度,对于每个等差数列会贡献 \(O(\text{点数})\) 的复杂度,一共 \(\log n\) 个等差数列,所以会贡献 \(O(n\log n)\) 的复杂度。

第四步:
第三步解决了从 \(F(i)\rightarrow F_{new}(i)\) 的问题,但是我们还需要让 \(F_{new}(i)\) 的模数变成第 \(k\) 个等差数列的 \(x\),而不是第 \(k-1\) 个等差数列的 \(x\)。例如当前模数(首项) \(x=15\),下一个等差数列模数(首项) \(x=12\)。怎么把 \(F(i)\) 的定义从 \(\bmod 15=i\) 的最小数,转化为 \(\bmod 12=i\) 的最小数,从而更方便用 \(\bmod 12\) 的 \(F(i)\) 推出属于 \(x=12\) 的 \(F_{new}(i)\)?

把 \(\bmod 15\) 的 \(F\) 记作 \(F(i)\),\(\bmod 12\) 的 \(F\) 记作 \(F'(i)\)。新的模数记作 \(x'\)。

这里 \(F'(i)\) 的更新取值分两种。

借一个具体的例子,比如 \(F(13)=28\)。

第一种:因为 \(28\bmod 12=4\),所以我们知道 \(F'(4)\) 可以取到 \(28\)。也就是如果 \(F(a)=b\),那 \(F'(b\mod x')\leftarrow b\)。

第二种:在 \(F\) 里 因为 \(F(13)=28\),所以 \(28+15\omega(\omega\ge 0)\) 都可以取到。在 \(F'\) 里对应着我们会用 \(F(13)+(15\bmod 12)\omega\) 去更新 \(F'\)。

考虑 \(F'\) 的更新建成同余最短路的图,实际上每个点只向后方第 \(3\) 个点连边。

理解一下。这里 \(F'\) 的同余最短路的建图和第三步的建图是不同的——\(F'\) 只有一种边,就是向后走 \(15\bmod 12=3\) 步的边。而第三步的建图有 \(\{x,x+d,\dots,x+td\}\) 一共 \(t+1\) 种向后走的边。所以 \(F'\) 的建图实际上就是一个环。

顺理成章地,沿用上面破环为链的想法。找到 \(\bmod 15\) 的所有 \(F(i)\) 里最小的,记作 \(F(mn)\)。以 \(mn\) 号点为起点破环为链,得到一条 \(mn\rightarrow mn+15\bmod 12\rightarrow mn+2\cdot (15\bmod 12)\rightarrow\cdots\) 的链,然后在这条链上走一遍,也就是 \(F'(mn+\alpha(15\bmod 12))\leftarrow F(mn)+15\alpha\)。

切换一次模数的复杂度是 \(O(\text{点数})\) 的。一共切换 \(\log n\) 次,也是 \(O(n\log n)\)。

总共 \(O(n\log n)\)。

标签:12,15,题解,bmod,论战,P4156,new,短路,等差数列
From: https://www.cnblogs.com/FLY-lai/p/18537078

相关文章

  • 题解:P11248 [GESP202409 七级] 矩阵移动
    笑点解析:这个人所在城市考试当天刮台风了,没考,免费送了一次12月的考试。设计这么一个东西:\(dp_{i,j}\)表示到格子\((i,j)\)的最大分数。本来还好,但现在的问题是,如果这个格子是‘?’,我哪儿知道到底可不可以变啊?万一变得太多了,那,那不就废了!万一少了,那我分不就没了?所以我们......
  • agc032 A~E 题解
    a倒推,每次删掉最后一个b[i]=i的即可b一开始发现可以构造完全二分图,使两边和同为S,这样每个点的和=对面二分图点的和=S,然后n=6和为奇数进一步发现可以直接分成A组组内和为B的组,然后组之间连边,此时S=(A-1)B,有AB=n(n+1)/2当n为奇数时取A=(n+1)/2,B=n,n单独一组其他大匹配小;n为偶数......
  • NOIP集训 P11071 「QMSOI R1」 Distorted Fate 题解
    题解:P11071「QMSOIR1」DistortedFate给定一个长度为\(n\)的数组\(A\),你需要完成以下\(q\)次操作。1.1lrx将\(A_i(l\lei\ler)\)异或上\(x\)。2.2lr求:\[(\sum_{i=l}^r\bigcup_{j=l}^iA_j)\bmod2^{30}\]其中\(\bigcup\)表示按位或。Input第一行输入......
  • [COCI2022-2023#5] Slastičarnica 题解
    前言题目链接:洛谷。题意简述一个长为\(n\)的序列\(\{a_n\}\)和\(q\)次操作,第\(i\)次操作中,你可以删除序列长为\(d_i\)的前缀或后缀,并需要保证删除的所有数\(\geqs_i\)。每次操作前,你可以选择任意长度的前缀或后缀,并将其删除,也可以不操作。请问,在你不能进行下一次操......
  • CodeforceTon Round 4 div1 + div2 题解
    题解A-EDreamissofar~A.BeautifulSequence检查每一位对应的数字是否小于等于位置,如果可以说明这个数字可以移动到对应位置上,遍历即可#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidsolve(){ intn; cin>>n; vector<int>a......
  • CF607B Zuma 题解
    CF607BZuma不知道为什么你谷会评蓝,这不是很基础的区间DP吗。Problem-607B-Codeforces题意简述消除回文子串的最小次数。思路对于区间\([i,j]\),如果它是回文的,那么消除它所需的次数是\(1\)。如果它不是回文的,但是\(a[i]==a[j]\),那么当区间\([i+1,j-1]\)被消除到只剩下......
  • [ARC158C] All Pair Digit Sums 题解
    C-AllPairDigitSums题意:设\(f(x)\)为\(x\)的数字和。例如\(f(158)=1+5+8=14\)。给定一个长度为\(N\)的正整数序列\(A\),求\(\sum_{i=1}^{N}\sum_{j=1}^{N}f(A_i+A_j)\)。分析:首先明确\(f(x)\)为\(x\)的数位和。举例情况:若有两个数分别为:\(12,21\)。\[f(......
  • QT中大量数据存储至excel的问题解决
            因为这个问题困扰了我很久,所以在这里记录一下,顺便给可能会遇到类似问题的人提供一点帮助。        在qt中,如果用C++处理数据保存到excel,正常来说在pro文件中添加axcontainer 然后就能够调用到excel,但是这只能适用于数量级没那么大时的需求。  ......
  • ffmpeg问题解决:Unrecognized option 'preset'. Error splitting the argument list: O
    来到这里,十有八九是手动编译安装的ffmpeg,在跑视频流程序或命令时出现这个问题。跟这个报错:ffmpeg:errorwhileloadingsharedlibraries:libx264.so.164:cannotopensharedobjectfile:Nosuchfileordirectory的错误本质是一样的,都是由于ffmpeg时使用到了libx264,而在......
  • 讲座の题解
    讲座配套题单的题解喵每题的文字解释会逐渐补充,如果有疑问直接私信喵目录讲座配套题单的题解喵目录A-看看你会不会用电脑B-求求你不要用内置函数C-GPAD-minE-for循环大神F-居然有人说这个是线性代数G-高三同学秒了H-无穷级数I-不要用内置函数......