SRM 537 500pt : KingXMagicSpells

問題概要

長さN(<50)の数列X(<10^9)がある。数列に対して等確率で

1. 各項に決まった値がxorされる。
2. 値にある置換が施される。

のどちらかの操作が行われる。K(<50)回この処理が繰り替えされた後のX[0]の期待値を求める問題。

解法

xorとかはビット毎にばらしてやれば良い。後は確率のDPをやればよい。「確率で」やると考えた方が分かりやすく、本当は同じことをしているはずなのに「期待値で」考えるとちょっと考え辛かった。計算量を落とす工夫とかは特に必要ない。

acceptされたコード

時間がなかったのでデバッグコードとか全部残してある。

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAX_N = 50;
const int MAX_K = 50;
int C;
int posi[MAX_N + 1][MAX_N];
double dp[MAX_K + 1][MAX_N + 1][MAX_N]; //(day, perm, i)
double dp2[MAX_K + 1][MAX_N + 1];

int dbg;

struct KingXMagicSpells {

	double expectedNumber(vector <int> ducks, vector <int> spellOne, vector <int> spellTwo, int K) {
		double ret = 0.0;
		const int N = ducks.size();

		for(int i=0; i<N; i++){
			posi[0][i] = i;
		}
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				posi[i+1][spellTwo[j]] = posi[i][j];
			}
		}

		for(int i=1; i<=N; i++){
			if(posi[i][0] == 0){
				C = i;
				break;
			}
		}

		//printf("C:%d\n", C);

		for(int i=0; i<31; i++){
			//build
			vector<int> ds(N), spells(N);
			for(int j=0; j<N; j++){
				ds[j] = (ducks[j]>>i)&1;
				spells[j] = (spellOne[j]>>i)&1;
			}
			ret += calc(ds, spells, spellTwo, K) * (1LL<<i);
		}

		return ret;
	}


	//0番目の期待値を返す。
	double calc(const vector<int>& ds, const vector<int>& xors, const vector<int>& perms, const int K){
		memset(dp, 0, sizeof(dp));
		memset(dp2, 0, sizeof(dp2));
		const int N = ds.size();
		if(0 && dbg == 0){
			for(int i=0; i<N; i++){
				printf("%d, ", xors[i]);
			}puts("");
		}
		for(int i=0; i<N; i++){
			dp[0][0][i] = ds[i];
		}
		dp2[0][0] = 1.0;

		for(int i=0; i<K; i++){
			for(int j=0; j<C; j++){
				dp2[i+1][(j+1)%C] += 0.5 * dp2[i][j];
				dp2[i+1][j] += 0.5 * dp2[i][j];

				//xor
				for(int k=0; k<N; k++){
					if(xors[k] == 0){
						dp[i+1][j][k] += 0.5 * dp[i][j][k];
					}
					else{
						dp[i+1][j][k] += 0.5 * (dp2[i][j] - dp[i][j][k]);
					}
				}

				//perm
				for(int k=0; k<N; k++){
					dp[i+1][(j+1)%C][perms[k]] += 0.5 * dp[i][j][k];
				}
			}
		}

		if(0 && dbg < 1){
			int q = 0;
			for(int i=0; i<K; i++){
				for(int j=0; j<C; j++){
					printf("%f, ", dp[i][j][q]);
				}puts("");
				q = perms[q];
			}
		}

		double ret = 0.0;
		int p = 0;
		for(int i=0; i<C; i++){
			if(0 && dbg < 3)printf("p:%d\n", p);
			//ret += dp2[K][i] * dp[K][i][0];
			ret += dp[K][i][0];
		}
		if(0 && dbg < 3){
			printf("ret: %f\n", ret);
		}
		dbg++;
		return ret;

	}

};