SRM 471 div2 500

Problem Statement
    
Elly is great fan of consistency. She would like to have order in even the simplest things in life – like listening to music.  
She has chosen several songs from which she wants to compose a playlist. The names of these songs are given in vector  songs, where each element is the name of a single song. 
Each name is unique and consists of at least three lowercase Latin letters. 
 A playlist is a sequence containing exactly K song names from songs. Each song from songs can be included zero, one or more times into a playlist. 
For each song in her playlist (except the last one), Elly wants the transition from this song to the next one in the playlist to be smooth. 
She calls transition from one song to another smooth if the substring formed by the first three letters of the name of the new song is the same as the substring formed by the last three letters from the name of the previous song. 
For example valid smooth transitions are from "xxxabc" to "abcyyy", from "entersandman" to "maneater", or from "heavensalie" to "liebe". 
On the other hand invalid transitions are from "yyydefg" to "defgyyy", from "toxicity" to "citylights", from "fadetoblack" to "breakingthehabit", from "hello" to "lol" or from "abbccddd" to "bcda".  
Elly wonders how many different playlists with exactly K songs she can make from the given songs, while respecting her wish to have smooth transition between each two consecutive ones. Since this number can be quite large, return its remainder when divided by 1,000,000,007. 
Two playlists are considered different if there is an index i such that the i-th songs in these playlists are different.
Definition
    
Class:
EllysPlaylists
Method:
countPlaylists
Parameters:
vector , int
Returns:
int
Method signature:
int countPlaylists(vector  songs, int K)
(be sure your method is public)
    

Constraints
-
K will be between 1 and 1000, inclusive.
-
songs will contain between 1 and 50 elements, inclusive.
-
Each element of songs will contain between 3 and 20 characters, inclusive.
-
Each element of songs will consist of lowercase Latin letters ('a'-'z') only.
-
All elements of songs will be distinct.
Examples
0)

    
{ "abcxxx", "xxxabc", "entersandman", "toxicity", "maneater", "heavensalie",
  "liebe", "citylights", "fadetoblack", "breakingthehabit", "yyydefg", "defgyyy" }
2
Returns: 5
The possible pairs are {"abcxxx", "xxxabc"}, {"xxxabc", "abcxxx"}, {"entersandman", "maneater"}, {"heavensalie", "liebe"}, and {"defgyyy", "yyydefg"}. Note that the order of the songs is important.
1)

    
{ "aaaaaa", "aaabcd", "bcdaaa" }
4
Returns: 13
One song can be used more than once in a playlist.
2)

    
{ "aaa", "aaaa", "aaaaa" }
3
Returns: 27
Aaaaaaa...
3)

    
{ "elly", "looks", "lovely" }
1
Returns: 3
Each song is a valid playlist.
4)

    
{ "life", "universe", "everything" }
42
Returns: 0
No valid sequence of 42 songs exists.
5)

    
{ "aaaaaaaaa", "aaabbbaaa", "aaacccaaa", "aaadddaaa", "aaaeeeaaa", "aaafffaaa" }
12
Returns: 176782322
The answer can be quite large, so don't forget to return only its remainder.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

こちらが自分の書いた回答。
こういうときはメモ化、あとは、数が大きくなりそうだったので、たすごとにDIVIDEする。

class EllysPlaylists {
private:
	bool compare(string& front, string& back);
	public:
	int countPlaylists(vector  songs, int K) {
		int num = songs.size();
		int const DIV = 1000000007; //1,000,000,007
		vector suit[num];
		for(int i = 0; i < num; i++) {
			for(int j = 0; j < num; j++) {
				if(compare(songs[i], songs[j])) {
					suit[i].push_back(j);
				}
			}
		}
		//memo
		int dp[K + 1][num];
		memset(dp, 0, sizeof dp);
		//Init
		for(int i = 0; i < num; i++) {
			dp[1][i] = 1;
		}
		for(int i = 2; i <= K; i++) {
			for(int j = 0; j < num; j++) {
				for(vector::iterator k = suit[j].begin();k != suit[j].end() ; k++) {
						dp[i][j] += dp[i-1][*k];
						dp[i][j] %= DIV;
				}
			}
		}
		int ans = 0;  //return
		for(int i = 0; i < num; i++) {
			ans += dp[K][i];
			ans %= DIV;
		}
		return ans;

	}
};
//call by reference!!
bool EllysPlaylists::compare(string& front, string& back) {
	int sz_front = front.length();
	if(front.substr(sz_front-3) == back.substr(0, 3)) {
			return true;
	}
	return false;
}

自分的には、iteratorの部分の書き方がみそです。
いちいち、ifとか書かなくていいので、見通しが気持ちすっきりします。
メモ化も自分でやってみて、コツをつかんできてる？？