TopCoder SRM 537 Div1 Medium KingXMagicSpells

これも他の回答を参考にしてしまった。
http://community.topcoder.com/stat?c=problem_statement&pm=11822

問題

初期状態でN要素の変数duck[i]がある。
ここで、以下の処理のいずれかを等確率で計K回行う。

• 各duck[i]を(duck[i] xor spellOne[i])で置き換える。
• 各duck[i]をduck[spellTwo[i]]に移動する。spellTwoは0～(N-1)のpermutationなので、duck[i]を並べ替えることに相当する。

最終的にduck[0]の期待値を求めよ。

解法

上記処理を巻き戻すことを考える。
すなわち、duck[0]が元々どのduck[x]から来て、途中spellOne[y]とのxorを何度行ったか考える。
ただし、duck[i]の最大値は10^9であり、これらをすべてDPで処理することはできない。

しかし、上記２処理はいずれもduck[i]の入れ替えとduck[i]のxor処理である。
よって、上記２処理を２進数の桁別において、spellOneとのxorかspellTwoの逆向きへの移動のどちらかを合計K回行い、最終的なduck[0]の各桁の期待値を求めればよい。

class KingXMagicSpells {
	public:
	int N;
	double expectedNumber(vector <int> ducks, vector <int> spellOne, vector <int> spellTwo, int K) {
		int R[51];
		int N=ducks.size();
		int i,j,x,y;
		ll dp[51][51][2];
		
		FOR(i,N) R[spellTwo[i]]=i;
		
		double ret=0;
		FOR(i,30) {
			ZERO(dp);
			dp[0][0][0]=1;
			FOR(j,K) {
				FOR(x,N) FOR(y,2) {
					dp[j+1][x][y^((spellOne[x]>>i)&1)] += dp[j][x][y];
					dp[j+1][R[x]][y] += dp[j][x][y];
				}
			}
			FOR(x,N) ret+=dp[K][x][((ducks[x]>>i)&1)^1]*pow(2,i-K);
		}
		return ret;
		
	}
}

まとめ

桁別に行うことがさらっと思い浮かばなかった…。