… \u7ed9\u5b9a\u4e00\u4e2a\u521d\u59cb\u57fa\u56e0\uff0c\u57fa\u56e0\u6bcf\u8f6e\u6bcf\u6b21\u4f1a\u5728\u540e\u9762\u6dfb\u52a0 {a, b, c ,d} \u4e2d\u7684\u4e00\u4e2a\u5b57\u7b26\u5f62\u6210 4 \u4e2a\u65b0\u57fa\u56e0\u3002\u65e7\u57fa\u56e0\u5728\u5206\u88c2\u8fc7\u540e\u4f1a\u635f\u5931\u7b2c\u4e00\u4e2a\u5b57\u7b26\u3002\u3002\u3002\u3002
\n\u6709 n \u7ec4\u6709\u5bb3\u57fa\u56e0\uff0c\u5982\u679c\u51fa\u73b0\u4e86\u6709\u5bb3\u57fa\u56e0\u4f5c\u4e3a\u5b50\u4e32\u5219\u4e22\u5165\u533b\u9662\u3002\u3002
\n\u5982\u679c\u4e00\u4e2a\u57fa\u56e0\u957f\u5ea6\u53d8\u4e3a 0 \u5219\u88ab\u4e22\u5165\u56de\u6536\u573a\u3002\u3002
\n\u95ee\u6700\u540e\u5206\u522b\u6709\u591a\u5c11\u57fa\u56e0\u4e22\u5165\u533b\u9662\u591a\u5c11\u57fa\u56e0\u4e22\u5165\u56de\u6536\u573a\u3002\u3002\u3002
\n( .. p <= 100, n <= 100, \u03a3 = {a,b,c,d} .. )\n\n<\/p>\n
dp[i][j][k] \u8868\u793a\u7ecf\u8fc7 i \u5929\uff0c\u5f53\u524d\u5728\u81ea\u52a8\u673a\u4e0a\u4f4d\u7f6e\u4e3a j\uff0c\u4e32\u7684\u5b9e\u9645\u957f\u5ea6\u4e3a k \u65f6\u7684\u72b6\u6001\u3002<\/p>\n
\r\n\r\n\/**********************************************************************************\/\r\n\/* Problem: b179 "\u7a7a\u7f50 Cans" from CSAPC'08 Problem Setter: Akira Nanase *\/\r\n\/* Language: CPP (2909 Bytes) *\/\r\n\/* Result: AC judge by zeroserver@ZeroJudge *\/\r\n\/* Author: lychees at 2011-08-29 01:02:15 *\/\r\n\/**********************************************************************************\/\r\n\r\n\r\n\/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **\/\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\n\r\nusing namespace std;\r\n\r\n#define REP(i, n) for (int i=0;i<int(n);++i)\r\n#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)\r\n#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)\r\n#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)\r\n#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)\r\n#define DO(n) while(n--)\r\n#define DO_C(n) int n____ = n; while(n____--)\r\n\r\ntemplate<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}\r\ntemplate<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}\r\ntemplate<class T> inline void RD(T &x){char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';}\r\ninline int RD(){ int x; RD(x); return x;}\r\n\r\nconst int MOD = 10007;\r\ninline void INC(int &a, int b){a += b; if (a >= MOD) a -= MOD;}\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 1510, M = 100, L = 102, Sigma = 26, SIGMA = 4;\r\nint dp[2][N][L]; int trie[N][Sigma], fail[N], len[N] = {1}, cnt[N], visited[N], u, cz, op, tot;\r\nchar str[M]; int n, s;\r\n\/\/ AC-automation\r\n\r\n#define v trie[u][c]\r\n#define f trie[fail[u]][c]\r\n#define Q visited\r\n\r\ninline int New_node(){\r\n fail[tot] = cnt[tot] = 0, RST(trie[tot]);\r\n return tot++;\r\n}\r\n\r\ninline void Build(){\r\n cz = op = u = 0; REP(c, Sigma) if (v) Q[op++] = v;\r\n\r\n while (cz < op){\r\n u = Q[cz++]; REP(c, Sigma)\r\n if (v) fail[Q[op++] = v] = f, cnt[v] += cnt[fail[v]];\r\n else v = f;\r\n }\r\n}\r\n\r\n#define c str[i] - 'a'\r\n\r\nbool _first;\r\ninline void Insert(){\r\n u = 0; REP_C(i, strlen(str)){\r\n if (cnt[v]) return; \/\/Prefix Cut ..\r\n if (!v) len[v = New_node()] = i + 1;\r\n u = v;\r\n }\r\n\r\n if (_first) _first = false, dp[0][s = u][len[u]] = 1;\r\n else ++cnt[u];\r\n}\r\n\r\n#undef c\r\n#undef f\r\n\r\nvoid Init(){\r\n RST(dp[0], trie[0]), tot = 1, _first = true, Insert(), RD(n);\r\n DO_C(RD()) scanf("%s", str), Insert(); Build();\r\n}\r\n\r\n#define u Q[i]\r\n#define f fail[u]\r\n#define d dp[q][u][j]\r\n\r\nvoid Run(){\r\n op = 0; REP(i, tot) if (!cnt[i]) Q[op++] = i;\r\n\r\n while (s && !cnt[s]) s = fail[s];\r\n if (s){puts("0 1"); return;}\r\n\r\n int p = 0, q, a = 0, b = 0;\r\n DO(n){\r\n\r\n q = p, p ^= 1, RST(dp[p]);\r\n\r\n REP(i, op) FOR_1(j, len[u], 100) if (d){\r\n REP(c, SIGMA) if (cnt[v]) INC(b, d); else INC(dp[p][v][j+1], d);\r\n if (j > len[u]) INC(dp[p][u][j-1], d);\r\n else if (cnt[f]) INC(b, d); else INC(dp[p][f][j-1], d);\r\n }\r\n INC(a, dp[p][0][0]);\r\n }\r\n\r\n\r\n printf("%d %d\\n", a, b);\r\n}\r\n\r\n\r\nint main(){\r\n\r\n \/\/freopen("in.txt", "r", stdin);\r\n\r\n while (scanf("%s", str) != EOF){\r\n Init(); Run();\r\n }\r\n}\r\n<\/pre>\nExternal link: <\/h3>\n