10625:GNU = GNU'sNotUnix

問題文
http://uva.onlinejudge.org/external/106/10625.html

(1文字)->(文字列)
のように変換表が与えられる。
さらに、
(文字列) (1文字 x) (数字 n)
のようにクエリが与えられるので、文字列を変換表に従ってn回変換した時、文字列中に現れる文字xの個数を求めよ。

動的計画法で解いた。
dp[ ステップ数 ][ 文字 ] := 個数
v[ 文字 j ][ 文字 k ] := jを変換したときkができる個数
として、
i回目に現れるkの個数は
(i-1回目のjの個数)*(jを変換したときkができる個数)
だから基本は
dp[ i ][ k ] += dp[ i-1 ][ j ] * v[ j ][ k ]
で計算する。全てのv[ j ][ k ]が0だった時は
変換されないので前のステップでの文字がそのまま残る。つまり
dp[ i ][ j ]+=dp[ i-1 ][ j ]

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
 
typedef unsigned long long ull;
 
ull dp[10001][128];

int main(void){
  int T,R;

  cin >> T;
  while(T--){
    int v[128][128];
    fill(v[0],v[128],0);

    cin >> R;
    cin.ignore();

    for(int i=0;i<R;i++){
      string str,to;
      char from;

      getline(cin, str);

      from=str[0];
      to=str.substr(3);

      for(int i=0;i<to.size();i++)
	v[from-33][to[i]-33]++;
    }
    
    int Q;
    cin >> Q;
    while(Q--){
      string source;
      char target;
      int t;
       
      cin >> source >> target >> t;
      
      fill(dp[0],dp[10001],0);      
 
      for(int i=0;i<source.size();i++)
	dp[0][source[i]-33]++;
      
      for(int i=1;i<=t;i++){
	for(int j=0;j<95;j++){
	  if(dp[i-1][j]<=0)continue;

	  bool fg=false;
	  for(int k=0;k<95;k++){
	    if(v[j][k]>0)fg=true;
	    dp[i][k]+=dp[i-1][j] * v[j][k];
	  }
	  if(!fg)dp[i][j]+=dp[i-1][j];
	}
      }
      cout << dp[t][target-33] << endl;
    }
  }
  return 0;
}