Description
给你前alphabet个小写字母组成的字符集, 以及n个单词, 定义一个串s的禁忌值为 (sum_{i } [s[i] == Taboo[i]]) , Taboo[i]为第i个单词,现在给定一个长度len,求随机一个用字符集生成的len长度的串的禁忌值的期望.
Solution
听说出题人卡double的精度,所以只能用long double
考虑一个当串给定时如何求禁忌值, 我们将所有单词投影到数轴上, 这就变成一个贪心, 即取尽量多的线段, 使他们互不相交. 因此我们只要建立一个AC自动机, 然后在自动机上走,碰到一个单词节点就返回根节点,并且ANS++,就可以模拟贪心的过程.(因为我们贪心是按照左端点排序,所以先在AC自动机里匹配的一定是左端点靠前的串).
考虑一个经典问题:给定一个图,求从u到v刚好经过m条边的路径条数.(n <= 100, m <= 1e9)
结论:只要把邻接矩阵处理出来,然后求它的n次方后的矩阵中, (a[u][v])的值.
证明:考虑只经过一条边, 那么直接输出(a[u][v])即可,在两条边的情况中,有 (ans = sum_{i = 1}^{n} a[u][i] * a[i][v])
只要枚举u到v的中转点,然后计算即可. 可以发现这正好是矩阵乘法的定义. 那么求邻接矩阵的k次幂就是两点k步的路径条数.
所以用(a[u][v])设为u一步到v的期望, 那么邻接矩阵自乘k次后也就是u到v走k步的期望值.
我们把AC自动机建出来,并设定一个终点,然后每走到一个节点就设定当前节点到它所有儿子的一步期望为(1.0/alphabet), 走到一个标有单词的节点.我们就设定它到根节点与终点的一步期望为(1.0/alphabet),然后矩阵乘法即可.
要注意AC自动机上如果一个节点的fail节点是单词节点,那么他本身也是单词节点.
这样我们就不用跳出一个点的子树, 并且也不会给fail的子树加期望加重复.
Codes
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
typedef long long LL;
typedef long double LD;
int read() {
int x = 0, flag = 1;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') flag *= -1;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << 3) + (x << 1) + ch - 48;
ch = getchar();
}
return x * flag;
}
void write(LL a) {
if(a >= 10) write(a / 10);
putchar(a % 10 + '0');
}
#define Maxn 6
#define Maxc 109
struct matrix {
LD data[Maxc][Maxc];
matrix operator * (const matrix b) const {
matrix c;
rep(i, 0, Maxc - 1)
rep(j, 0, Maxc - 1) {
c.data[i][j] = 0;
rep(k, 0, Maxc - 1)
c.data[i][j] += (*this).data[i][k] * b.data[k][j];
}
return c;
}
matrix operator ^ (int times) const {
matrix res, base = (*this);
rep(i, 0, Maxc - 1)
rep(j, 0, Maxc - 1) res.data[i][j] = (i == j);
while(times) {
if(times & 1) res = res * base;
base = base * base;
times >>= 1;
}
return res;
}
}a, b;
#define Maxl ((Maxn) * 16 * 1009)
int vis[Maxl];
int n, len, alphabet;
namespace AC_DFA {
int v[Maxl], t[Maxl][26], cnt = 1, fail[Maxl];
void insert(char str[]) {
int len = strlen(str), cpos = 1;
rep(i, 0, len - 1) {
int id = str[i] - 'a';
if(!t[cpos][id]) t[cpos][id] = ++cnt;
cpos = t[cpos][id];
}
v[cpos] = 1;
}
queue <int> q;
void get_fail() {
q.push(1);
while(!q.empty()) {
int u = q.front(); q.pop();
v[u] |= v[fail[u]];
int pos;
rep(i, 0, alphabet - 1) {
pos = fail[u];
while(pos && !t[pos][i]) pos = fail[pos];
if(t[u][i]) {
fail[t[u][i]] = pos ? t[pos][i] : 1;
q.push(t[u][i]);
}else t[u][i] = pos ? t[pos][i] : 1;
}
}
}
void make_InitalMatrix() {
while(!q.empty()) q.pop();
q.push(1), vis[1] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
rep(i, 0, alphabet - 1) {
if(!vis[t[u][i]]) vis[t[u][i]] = 1, q.push(t[u][i]);
if(v[t[u][i]]) {
a.data[u][cnt + 1] += (LD)1.0 / alphabet;
a.data[u][1] += (LD)1.0 / alphabet;
} else a.data[u][t[u][i]] += (LD)1.0 / alphabet;
}
}
a.data[cnt + 1][cnt + 1] = 1;
}
};
char s[Maxn][16];
int main() {
n = read(), len = read(), alphabet = read();
rep(i, 1, n) scanf("%s", s[i]), AC_DFA :: insert(s[i]);
AC_DFA :: get_fail();
AC_DFA :: make_InitalMatrix();
b = a ^ len;
printf("%.6Lf
", b.data[1][AC_DFA :: cnt + 1]);
return 0;
}