May 20, 2024
#include <lastweapon/string>
#include <lastweapon/number>
using namespace lastweapon;
int Z;
int f() {
<pre><code>int n; RD(n); VI P; DO(n) P.PB(RD());
auto pi = kmp(P);
Int z = 0; while (n) {
z += pow(Int(Z), n); n = pi[n-1] + 1;
}
return z;
</code></pre>
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
<pre><code>MOD = 10000; RD(Z); Rush {
printf(&quot;%04d\n&quot;, f());
}
</code></pre>
}
经典问题！最后代码非常简单，但并不是十分显然，令人浮想联翩。
首先最朴素的自动机 dp 也是可以推出来的！直接设状态 f[i] 表示匹配上前 i 个字符之后剩余的期望步数。
利用 trans 数组建立转移方程，但是这个方程是有环的，朴素做法高斯消元 O(n3)，但我们可以进一步挖掘这类矩阵的性质。
类似调色板那个题，我们也可以差分之后推推推直接得到上面的 O(n) 做法。
但是这样需要一定的代数底力，另一个相对更简单的做法是使用概率生成函数，但是这个做法也不能帮助我们一眼看出为什么这个题会和 border 联系如此紧密。
更高级的做法是构造一个公平博弈，来了一大堆 ASC 42 B 那种赌局，最后将期望步数等价于游戏结束时剩余赌徒的收益。
这个做法背后的理论基础是鞅论，有时能够帮我们一眼看出这类题的答案。
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。