TopCoder SRM 342 Div1 Medium ReverseResources

問題

文字列strおよび、要素数nの文字列の配列resources[]が与えられる。
文字列strは、resourcesから次のようにして作った文字列である。

  • resourcesの要素どれか一つresources[i]から出発する
  • 文字列中の"%s"を、resourcesの別の要素に置換する
  • 上の操作を繰り返す

このとき、resourcesからstrを作る作り方は何通りあるか、mod 10^9+7で求めよ。
ただし、resourcesに重複する要素が含まれていても、それらは別々のものとして数えるものとする。

制約条件

strの長さ≦30
resourcesの要素≦50
resoures[i]の長さ≦50
resources[i]は%sだけであることはない

方針

動的計画法(メモ化再帰)による。
rec(i,j,id,pos)を、
元の文字列i文字目からj文字目までを作っていて、
現在resources[id]のpos番目の文字までを作っている状態の場合の数とする。


ただし、idがnのときは、次にどのresources[i]の要素も使えるとする。
これでrec(0,元の文字列の長さ,n,0)を求めてやればよい。


再帰関数の中では、
idがnより小さい場合は、strのl番目の文字と、resources[id]のpos番目の文字が一致しているかを見る。
idがnだったら、resourcesの全てを使ってみて、それぞれの場合の数を合計する。

ソースコード

void replace(string &a,string b,string c){
	for(int p=0;(p=a.find(b,p))!=a.npos;p++)
		a=a.substr(0,p)+c+a.substr(p+b.size());
}
const int mod=1000000007;
string s;
vs v;
int n,m,len[51];
int dp[31][31][51][51];
int rec(int l,int r,int id,int pos){
	int &res=dp[l][r][id][pos];
	if(res>=0)return res;
	res=0;
	
	if(l>r)return 0;
	if(l==r)return res=id!=n&&pos==len[id];
	
	if(id==n){
		rep(i,n)(res+=rec(l,r,i,0))%=mod;
		return res;
	}
	
	if(pos==len[id])return 0;
	
	if(v[id][pos]=='@'){
		for(int i=l+1;i<=r;i++){
			res+=(ll)rec(l,i,n,0)*rec(i,r,id,pos+1)%mod;
			res%=mod;
		}
		return res;
	}
	if(s[l]!=v[id][pos])return 0;
	return res=rec(l+1,r,id,pos+1);
}

class ReverseResources {
	public:
	int findDecompositions(string str, vector <string> resources) 
	{
		s=str;
		v=resources;
		
		n=v.size();
		m=s.size();
		rep(i,n){
			replace(v[i],"%s","@");
			len[i]=v[i].size();
		}
		memset(dp,-1,sizeof(dp));
		
		return rec(0,m,n,0);
	}
};