题意:压缩字符串,把字符串分成若干个子串,每个子串可以被压缩成“循环次数 \(+\) 循环节”的形式,求最小长度。
dp 求 lcp
先 \(O(n^2)\) dp 求出所有后缀对的 \(lcp_{x,y}\),(也可以 \(\text{SA}\) \(O(\log n)\) 求,但是本题 \(n=8000\) 还有 \(\dfrac{1}{2}\) 的常数,没必要这么做。
然后我们设 \(dp_{i}\) 表示当前 \(i-1\) 前面的位置都已经压缩完成的最小长度。枚举最小循环节长度 \(j\),一直往后 \(dp\),直到 \(lcp_{i,r}\lt j\) 为止。
对其中所有的 \(i+kj\),将 \([i,i+kj-1]\) 压缩成一个子串进行转移,转移到 \(i+kj\)。提前预处理出每个循环次数和字符串长度的对应关系 \(O(1)\) 转移到 \(i+kj\),转移复杂度 \(O(n\log n)\),总的复杂度是 \(O(n^2\log n)\) 的,但是常数较小,可过。
双模哈希
首先,显而易见的贪心,如果当前确定了要把 \([l,r]\) 压缩成一个子串,则一定选择最小的循环节。因为选择更大的循环节,循环节的长度增加是循环次数长度减少的 \(10\) 倍。
然后,考虑如何计算 \([l,r]\) 中的最小循环节。
我们考虑计算 \(f_{l,r}\) 表示以 \([l,r]\) 为第一个循环节,最多往后循环次数。我们可以从后往前枚举左端点,然后只考虑 \(f_{r+1,r+(r-l+1)}\),因为这是我们从 \(f_{l,r}\) 往后拓展的必经之路。我们可以用字符串哈希 \(O(1)\) 判断两个区间是否相等,从而判断能否从后面进行转移,如果可以,\(f_{l,r}=f_{r+1,r+(r-l+1)}+1\),否则,\(f_{l,r}=1\)。
接下来有一个假做法,就是枚举 \(i\) 之后的最小循环节长度,然后贪心选取尽可能多的循环次数。但是这样会 WA,因为我们可能要留一点字符给后面的循环节。
我们考虑计算 \(g_{l,r}\) 表示 \([l,r]\) 的最小循环节。我们的思路是从小到大枚举,然后使用 \(f_{l,r}\) 往后延申直到超出 \(f_{l,r}\) 的次数。这样就是对每个 \([l,r]\) 都循环 \(f_{l,r}\) 次对 \(g_{l,l+k\times len}\) 进行贡献。复杂度是 \(O(n^2\log n)\),和前面的做法没什么区别。
但是我们如果使用一些线性筛的思想,使得每个 \(g_{l,r}\) 只被自己的最小循环节贡献,如果当前的循环节已经存在循环节,就不往更大的区间进行贡献。我们发现这是正确的。
首先,如果一个长度 \(n\) 的区间存在两种循环节,长度分别是 \(x\) 和 \(y\),那么一定存在 \(\gcd(x,y)\) 长度的循环节。我们假设 \(x<y\),考虑所有长度为 \(y\) 的循环节将所有长为 \(\gcd(x,y)\) 的单元分成 \(n/y\) 段,每段都有 \(y\) 个不同的,而划分出 \(y\) 个剩余类,例如 0 1 2 0 1 2 0 1 ...
。然后考虑 \(x\) 对 \(y\) 的覆盖,因为 \(x'=\dfrac{x}{\gcd(x,y)}\) 和 \(y'=\dfrac{y}{\gcd(x,y)}\) 是互质的,所以其唯一重合的地方是 \(n'=\dfrac{n}{\gcd(x,y)}\)。那么从 \(0\) 开始每次跳 \(x'\) 遍历可以遍历 \(y'\) 的整个剩余系。
或者说,对 \(y'\) 的剩余系而言,因为 \(x'\) 和 \(y'\) 互质,所以设 \(S\) 是模 \(y\) 的剩余系,则 \(xS=S\),即\(0,x',2x',3x',\cdots,(y'-1)x'\) 模 \(y'\) 两两不同余。则所有模 \(x'\) 意义下的等价类 \(0\) 都两两不同的对应了模 \(y\) 意义下的所有等价类恰好一次,得到所有 \(\gcd(x,y)\) 长的单元都是相同的,则存在长度 \(\gcd(x,y)\) 的循环节。
那么,任何的区间 \([l,r]\) 都存在唯一最小的循环节 \(s\),使得任意其他循环节 \(t\),都存在 \(k|s|=|t|\)。那么在 \(s\) 贡献到 \([l,r]\) 的同时,其其他循环节也都被贡献到了,由于先枚举小的区间,我们就不会调用 \([l,r]\) 的任意其他循环节覆盖别人,所以计算 \(g_{l,r}\) 的过程中,每个\([l,r]\) 只被扫到一次,总复杂度 \(O(n^2)\)。
最后,设 \(dp_i\) 表示 \(i-1\) 以前都成功配对,然后枚举当前压缩的大区间右端点 \(r\),使用其最小循环节进行贡献,预处理每个数字对应的长度,就可以做到 \(O(1)\) 计算单个转移,总的转移是 \(O(n)\) 的,这一环节的复杂度也是 \(O(n^2)\)。
从而,整个算法的复杂度是 \(O(n^2)\)。注意哈希和匹配的常数较大,可能成为算法瓶颈(大常数 \(O(n^2)\))
const ll P1=998244353,P2=1000000007,S1=114,S2=191;
ll h1[8005],h2[8005],pw1[8005],pw2[8005],ipw1[8005],ipw2[8005];
int cnt[8005][8005],bit[8005],dp[8005];
int f[8005][8005];
st s;int n;
inline pll hsh(int l,int r){
ll r1=(h1[r]-h1[l-1]*pw1[r-l+1]%P1+P1)%P1;
ll r2=(h2[r]-h2[l-1]*pw2[r-l+1]%P2+P2)%P2;
return pll(r1,r2);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>s;n=s.size();s='$'+s;
rp(i,n)h1[i]=(h1[i-1]*S1+s[i]-'a')%P1;
rp(i,n)h2[i]=(h2[i-1]*S2+s[i]-'a')%P2;
pw1[0]=pw2[0]=ipw1[0]=ipw2[0]=1;
rp(i,n)pw1[i]=pw1[i-1]*S1%P1;
rp(i,n)pw2[i]=pw2[i-1]*S2%P2;
rep(i,1,9)bit[i]=1;
rep(i,10,99)bit[i]=2;
rep(i,100,999)bit[i]=3;
rep(i,1000,8000)bit[i]=4;
per(l,1,n)rep(r,l,n){
int len=r-l+1;cnt[l][r]=1;
if(r+len<=n&&hsh(l,r)==hsh(r+1,r+len))cnt[l][r]=cnt[r+1][r+len]+1;
}
dp[1]=0;
rep(i,2,n+1)dp[i]=1e9;
rep(l,1,n)rep(r,l,n)if(f[l][r]==0){
int len=r-l+1;
for(int i=1;l+i*len-1<=n&&i<=cnt[l][r];i++){
f[l][l+i*len-1]=i;
}
}
rep(l,1,n)rep(r,l,n)
dp[r+1]=min(dp[r+1],dp[l]+bit[f[l][r]]+(r-l+1)/f[l][r]);
cout<<dp[n+1]<<endl;
return 0;
}
//Crayan_r
标签:P1,String,复杂度,循环,CF825F,长度,8005,dp,Compression
From: https://www.cnblogs.com/jucason-xu/p/17149171.html