这个难度直接可以用dp去解决我们看
那么我们用代码表示这个字符的个数，那么从上就得出
可以看出从我们都可以直接从前一个继承过来，和我们单独去操作即可
所以我们遍历每一步然后对于每一步将字符串里的操作就行，我们只需要知道数量，并不需要知道具体位置。
所以时间复杂度就是
首先知道初级难度的用dp去维护，我们这里也是先去找子问题，看看能不能拆解出子问题：
假设经过过一次，之后变成和。问题就变成了计算替换(t-1)次的长度，加上，替换(t-1)次的长度。
那么我们还用表示字母替换次的长度
上面说的例子：
那么我们做推广一下：
设
$$ dp[i][j]=sum^{j+c}_{k=j+1}dp[i-1][k%26] $$
是为了这个阶段
初始状态：
最终结果$$sum_{j=0}^{25}dp[t][j] imes a[j]$$其中是中字母的出现次数
这个复杂度就是解决第一题的复杂度
$$ dp[i][1]=dp[i-1][2] $$
$$ dp[i][25]=dp[i-1][0]+dp[i-1][1] $$
用矩阵乘法表示：
$$ left[begin{array}{c} dp[i][0] \ dp[i][1] \ dp[i][2] \ vdots \ dp[i][23] \ dp[i][24] \ dp[i][25] end{array} ight]=left[begin{array}{ccccccc} 0 & 1 & 0 & 0 & cdots & 0 & 0 \ 0 & 0 & 1 & 0 & cdots & 0 & 0 \ 0 & 0 & 0 & 1 & cdots & 0 & 0 \ vdots & vdots & vdots & vdots & ddots & vdots & vdots \ 0 & 0 & 0 & 0 & cdots & 1 & 0 \ 0 & 0 & 0 & 0 & cdots & 0 & 1 \ 1 & 1 & 0 & 0 & cdots & 0 & 0 end{array} ight]left[begin{array}{c} dp[i-1][0] \ dp[i-1][1] \ dp[i-1][2] \ vdots \ dp[i-1][23] \ dp[i-1][24] \ dp[i-1][25] end{array} ight] $$
把上式中的三个矩阵记作
$$ A[i]=M imes A[i-1] $$
那么就有
$$ begin{align} A[t] &= M imes A[i-1] \ &= M imes M imes A[i-2] \ & ...\ &=M^t imes A[0] end{align} $$
其中$M^t$ 可以用矩阵快速幂计算。$A[0]$是长为26的列向量，值全为1，对应着
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/bcyy/16170.html