BZOJ_2272
可以用f[i][j][k]表示递推到第i个字符时，大写字符已经有了j个，且最后一个字符是k，这样总状态一共约有500*250*52，总的状态转移次数约有500*250*200，是可以承受的。
#include#include #include #include #define MOD 97654321int N, U, L, P, f[2][260][128];std::vector g[128];void init(){ N = U + L; char b[5]; for(int i = 0; i < 128; i ++) g[i].clear(); for(int i = 0; i < P; i ++) { scanf("%s", b); g[b[1]].push_back(b[0]); }}void solve(){ int cur = 0, ans = 0; memset(f[0], 0, sizeof(f[0])); for(int i = 'a'; i <= 'z'; i ++) f[0][0][i] = 1; for(int i = 'A'; i <= 'Z'; i ++) f[0][1][i] = 1; for(int i = 2; i <= N; i ++) { cur ^= 1; for(int j = 0; j <= U; j ++) { for(int k = 'A'; k <= 'Z'; k ++) { f[cur][j][k] = 0; if(j > 0) for(int t = 0; t < g[k].size(); t ++) f[cur][j][k] = (f[cur][j][k] + f[cur ^ 1][j - 1][g[k][t]]) % MOD; } for(int k = 'a'; k <= 'z'; k ++) { f[cur][j][k] = 0; for(int t = 0; t < g[k].size(); t ++) f[cur][j][k] = (f[cur][j][k] + f[cur ^ 1][j][g[k][t]]) % MOD; } } } for(int i = 'a'; i <= 'z'; i ++) ans = (ans + f[cur][U][i]) % MOD; for(int i = 'A'; i <= 'Z'; i ++) ans = (ans + f[cur][U][i]) % MOD; printf("%d\n", ans);}int main(){ while(scanf("%d%d%d", &U, &L, &P) == 3) { init(); solve(); } return 0;}