Uva 1358 KMP转移图加速DP + 马尔可夫过程 + 简单数学推导

题意：给定一个字符串S和字符集大小\(n\)。要求另生成一个字符串，它一开始为空，每次平均且独立地随机生成一个字符集中的字符添加到其末尾，生成出字串S时停下，求所生成字符串的长度的期望。

　　sol：一眼DP + KMP加速转移。又发现这是一个马尔可夫过程，可列出\(n\)个方程，暴力高斯消元求解之即可。

　　然而这题多推一步就有更简洁的做法。马尔可夫方程有两种形式。如果我们设\(d[i]​\)表示末尾生成出长度为\(i​\)的S前缀时，生成出S还需要的添加次数的期望值，则

\[ d[i] = 1 + \frac{d[i+1]}{n}+\frac{1}{n}\sum_{c'}{d[fail[i + c']]} \]

其中，\(c'\)表示除了\(S[i+1]\)之外的字符（S下标从1开始）。

　　另外一种是，我们设\(d[i]\)为末尾生成出长度为\(i\)的S前缀的添加次数的期望值。则

\[ d[i] = \frac{d[i+1]}{n}+\frac{1}{n}\sum_{c'}{d[fail[i + c']]} - 1 \]

变形后得到

\[ d[i+1] = (d[i] + 1)\times n - \sum_{c'}{d[fail[i + c']]} \]

显然\(d[0] = 0\)，从小到大枚举\(i\)和\(c\)进行DP即可。

　　代码如下，最后一组数据的答案后面不能输出空行。

#include <cstdio>
#include <cstring>
using namespace std;

 #define rep(i, a, b) for (int i = a; i <= b; i++)
 #define fill(a, x) memset(a, x, sizeof(a))
 #define read(x) scanf("%d", &x)

 typedef long long LL;
 
 const int N = 15;

 int T, kase = 0, n, m, f[N], a[N];
 LL d[N];
 char S[N];

 void get_fail(int *a, int *f, int n) {
    f[1] = f[2] = 1;
    rep(i, 2, n) {
        int j = f[i];
        while (j != 1 && a[j] != a[i]) j = f[j];
        f[i + 1] = a[j] == a[i] ? j + 1 : 1;
    }
 } 

 void solve() {

    if (kase) puts("");

    read(m);
    scanf("%s", S);
    n = strlen(S);
    rep(i, 1, n) a[i] = (int)S[i - 1] - 'A' + 1;

    fill(f, 0);
    get_fail(a, f, n);

    fill(d, 0);
    rep(i, 1, n) {
        LL &cur = d[i];
        cur =  m * (d[i - 1] + 1);
        rep(j, 1, m) {
            if (j == a[i]) continue;
            int k = i;
            while (k != 1 && a[k] != j) k = f[k];
            if (k == 1 && a[1] != j) k = 0;
            cur -= d[k]; 
        }
    }
    printf("Case %d:\n%lld\n", ++kase, d[n]);
 }

int main()
{
    read(T);
    while (T--) solve();
    return 0;
}
           

转载于:https://www.cnblogs.com/yearwhk/p/6203103.html