TopCoder SRM 599, Divisin 2, Level 3 : SimilarNames2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12871&rd=15711

概要

　相異なる複数の文字列と整数 L が与えられる。この文字列群の並び替えであって、L - 2 以下の各 i について i 番目の文字列が i + 1 番目の文字列のプレフィックスとなっているようなものの数を MOD で求めよ。

解法

　文字列の数を N とします。後ろの N - L 個の並びには制約が無いので、並べ方は明らかに ( N - L )! 通りです。どのような文字列集合を後半に配置したとしても同じです。これで、手前 L 個の並べ方の総数が分かれば全体を解けるようになりました。
　では、手前の並べ方について述べます。各文字列をノードとし、a /= b なる a, b であって a が b のプレフィックスであるときに a -> b の有向辺を張ったグラフを考えます。有向辺を辿ると文字列は長くなるので、このグラフに閉路は無く、DAG であることが分かります。求めたいものはこのグラフ上の長さ L - 1 のパスの総数なので、次のような DP を考えることができます。

• dp[ i 個繋げた ][ 末尾が j ] := 場合の数

初期状態は有効な全ての j について dp[ 0 ][ j ] = 1 です。状態遷移は一通りで、j /= k なる j, k について、j が k のプレフィックスとなっているときに dp[ i + 1 ][ k ] += dp[ i ][ j ] として更新します。計算が終わった後、有効な j について dp[ L - 1 ][ j ] の総和が前半部分の並べ方の総数です。
　最後に、DP で求めた数に ( N - L )! を掛ければ答えが求まります。

コード

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

const int MOD = 1000000007;

class SimilarNames2
{
public:
	int count( vector <string> names, int L )
	{
		const int N = names.size();

		VVI dp( L, VI( N, 0 ) );
		fill( ALL( dp[0] ), 1 );
		// dp[ i 個繋げた ][ j が末端 ] := 数

		REP( i, 0, L - 1 )
		{
			REP( j, 0, N )
			{
				REP( k, 0, N )
				{
					if ( j != k && names[k].find( names[j] ) == 0 )
					{
						( dp[ i + 1 ][k] += dp[i][j] ) %= MOD;
					}
				}
			}
		}

		LL res = accumulate( ALL( dp[ L - 1 ] ), 0LL ) % MOD;
		REP( i, 0, N - L )
		{
			( res *= i + 1 ) %= MOD;
		}
		return res;
	}
};