TopCoder SRM 689 Div2 Hard ColorfulGardenHard

これDiv2とはいえ900ptでいいんじゃないかな…。
https://community.topcoder.com/stat?c=problem_statement&pm=14247

問題

文字列Gを並べ替えたい。
並べ替えた後の文字列のうち、その際以下の条件を満たすものは何通りか。

• 同じ長さの文字列Fに対し、G[i]=F[i]となるiが1つもない
• 隣接する要素は一致しない

なお、並べ替え方が異なっても、結果得られる文字列が同一の場合、１つと数える。

解法

Gの長さが短いので、bitDPで解こう。
先頭から１文字ずつ決めていく。
dp(bitmask,last) := Gのうちbitmaskのたったビットに相当する文字列を使用し、かつ最後がG[last]であるような文字列の数

１点注意点は、同一文字列は多重カウントできない点。
これは同種の文字を使う際はそのうち左端の未使用文字から順に使う、といったルールを適用しながらDPすればよい。

ll dp[1<<16][16];
ll mo=1000000007;

class ColorfulGardenHard {
	public:
	int count(string G, string F) {
		int i,j;
		int N = G.size();
		
		sort(G.begin(),G.end());
		ZERO(dp);
		
		FOR(i,N) if((i==0 || G[i]!=G[i-1]) && G[i]!=F[0]) dp[1<<i][i]=1;
		for(int mask=1;mask<1<<N;mask++) {
			int num=__builtin_popcount(mask);
			FOR(i,N) if((mask&(1<<i)) && dp[mask][i]) {
				FOR(j,N) {
					if(mask&(1<<j)) continue;
					if(G[i]==G[j]) continue;
					if(j&&G[j]==G[j-1]&&((mask&(1<<(j-1)))==0)) continue;
					if(F[num]==G[j]) continue;
					(dp[mask | (1<<j)][j] += dp[mask][i])%=mo;
				}
			}
		}
		ll tot=0;
		FOR(i,N) tot += dp[(1<<N)-1][i];
		return tot%mo;
		
	}
}

まとめ

妙に簡単。