[TyvjP1519] 博彩游戏（AC自动机 + DP）

传送门

和bzoj1030一个德性

#include <queue> #include <cstdio> #include <cstring> #define N 500001 #define LL long long int m, n, r, cnt; LL f[61][N], ans, sum = 1; int next[N][10], fail[N]; bool val[N]; char s[N]; std::queue <int> q; inline void insert() val[now] = 1; } inline void make_fail() fail[next[now][i]] = next[fail[now]][i]; val[next[now][i]] |= val[next[fail[now]][i]]; q.push(next[now][i]); } } } int main() make_fail(); for(i = 1; i <= m; i++) sum *= r; f[0][0] = 1; for(i = 1; i <= m; i++) for(j = 0; j <= cnt; j++) for(i = 0; i <= cnt; i++) ans += f[m][i]; printf("%.5lf\n", double(sum ans) / double(sum)); return 0; }

　　

上一篇：[BZOJ1582] [Usaco2009 Hol]Holiday Painting 节日画画（线段树）

下一篇：[BZOJ1663] [Usaco2006 Open]赶集（spfa最长路）

---

DP AC自动机