• https://www.luogu.com.cn/problem/P4548
• https://www.luogu.com.cn/problem/P6835
• https://vjudge.net/problem/HDU-3992
• https://vjudge.net/problem/Gym-104551B
• https://vjudge.net/problem/HDU-3689
• https://leetcode.cn/problems/find-all-possible-stable-binary-arrays-ii/description/

#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(&quot;in.txt&quot;, &quot;r&quot;, stdin);
    //freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);
#endif

<pre><code>MOD = 10000; RD(Z); Rush {
    printf(&amp;quot;%04d\n&amp;quot;, f());
}
</code></pre>

}

经典问题！最后代码非常简单，但并不是十分显然，令人浮想联翩。
首先最朴素的自动机 dp 也是可以推出来的！直接设状态 f[i] 表示匹配上前 i 个字符之后剩余的期望步数。
利用 trans 数组建立转移方程，但是这个方程是有环的，朴素做法高斯消元 O(n3)，但我们可以进一步挖掘这类矩阵的性质。
类似调色板那个题，我们也可以差分之后推推推直接得到上面的 O(n) 做法。

但是这样需要一定的代数底力，另一个相对更简单的做法是使用概率生成函数，但是这个做法也不能帮助我们一眼看出为什么这个题会和 border 联系如此紧密。
更高级的做法是构造一个公平博弈，来了一大堆 ASC 42 B 那种赌局，最后将期望步数等价于游戏结束时剩余赌徒的收益。
这个做法背后的理论基础是鞅论，有时能够帮我们一眼看出这类题的答案。

dp

概率生成函数

鞅论

Posted by xiaodao
Category: 日常