TopCoder SRM 477 Div 2 Hard CarelessSecretary

問題概要

秘書がN人の大臣に手紙を配るのに、いくつか宛先を間違えた。
少なくともK人の大臣が間違った手紙を受け取るような場合の数を求めよ。

N≦1000,K≦12を満たす。

解法

残りのN-K人についての手紙の配り方は(N-K)!通り。

次にK人についての配り方を調べる。
K人の内、i人目までの手紙の配り方を、「K人の手紙をK人のうちの誰かに配ったかどうかをbit」とし、dp[i][bit]通りとする。

i人目の手紙の配り方は、K人以外の手紙を受け取る場合と、
K人の自分以外の誰かのうち、まだ手紙を配ってない人の手紙を受け取る場合の和。

以上のような漸化式を元にした動的計画法で解くことが出来る。
ソースにコメントをつけたので日本語での説明でわかりにくい場合そちらを参照。

ソースコード

const ll MOD=1000000007;
ll dp[1<<12][13];

ll F(int n)
{
	ll ret=1;
	rep(i,n)ret=ret*(n-i)%MOD;
	return ret;
}
class CarelessSecretary {
	public:
	int howMany(int N, int K) 
	{
		rep(i,1<<K)fill_n(dp[i],K+1,0);
		dp[0][0]=1;
		rep(i,K)rep(bit,1<<K)
		{
			rep(j,K)if(i!=j&&!(bit&1<<j))
			{//K人の誰かの手紙を貰う
				dp[bit|1<<j][i+1]=(dp[bit|1<<j][i+1]+dp[bit][i])%MOD;
			}
			int rest=N-K-i; //N-K人の手紙の内、まだ配ってない手紙がrest
			rep(j,K)if(bit&1<<j)rest++;
			//N-K人の誰かの手紙を貰う
			if(rest>=0)dp[bit][i+1]=(dp[bit][i+1]+dp[bit][i]*rest)%MOD;
		}
		
		ll ans=0;
		rep(i,1<<K)ans+=dp[i][K];
		
		return ans%MOD*F(N-K)%MOD;
	}
};