題意:給定一個字元串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