SRM 440 Div2 Hard WickedTeacher

与えられた数の組number[n]を、ランダムに並べてつなげ、１つの巨大な数にした時にそれがKで割り切れる確率を求めよ。
ただしK≦100、n≦15であり、number[i]のそれぞれは50桁以下であるとする。

全列挙は15!（約1兆）なのでなんらかの計算量削減が必要になる。
Kが100以下と小さいので、余りの場合の数が少ない（＝合流が多い）ことに注目してDPする。
つまり、n個のうちあるm個を使って余りkに至る場合の数をメモ化すれば良い。
（最大で2^15*100≒300万）

ただしこのDPをしてもnumber[i]をkで割った余りを1回ごとにナイーブに計算などとしていると、入力の大きいケースで時間切れになるため予め計算しておく必要がある。

while(!Q.empty())
//pair<n個のうちどれを使ったかをあらわすbit,そのときの余り>
{
	int cbit=Q.front().first,cmod=Q.front().second;
	Q.pop();
	
	rep(i,n)
	{
		if(1<<i&cbit)continue;
		int nbit=cbit|1<<i;
		int nmod=(MOD(i)+cmod*pw10(i))%K;
		
		if(dp[nbit][nmod])
		{
			dp[nbit][nmod]+=dp[cbit][cmod];
			continue;
//すでにその状態がqueueに入っているときは
//新たにqueueにpushしない。
		}
		dp[nbit][nmod]=dp[cbit][cmod];
		//入っていなかったらqueueにpush
		Q.push(mp(nbit,nmod));
	}
}

（DP部分のみ）

幅優先なので、m個を使った全ての場合を試した後でm+1個を使う場合のqueueが取り出される。
よって任意の時点でdp[ ][ ]はその状態に至る場合の数の合計を正しく表している。

最後に分数を出力するとき、分子分母を最大公約数で割る必要があるが、dp[ ][ ]も含めて全てlong longで計算しないとオーバーフローするので注意……