SRM537 Div1 Medium(500) KingXMagicSpells

KingXMagicSpells

ビットごとに分けて計算することができる。途中の計算はXORと移動だけ。平均も、例えばビットが1になる確率がそれぞれのビットで50%とすると、000=0₁₀ 50%、111=7₁₀ 50%でも、010=2₁₀ 50%、101=5₁₀ 50%でも平均は等しい。

#include <vector>
using namespace std;

class KingXMagicSpells{public:
double expectedNumber( vector <int> ducks, vector <int> spellOne, vector <int> spellTwo, int K )
{
    int n = (int)ducks.size();

    double ans = 0;

    for ( int i=0; i<31; i++ )
    {
        vector<vector<double> > T(K+1,vector<double>(n));
        for ( int j=0; j<n; j++ )
            T[0][j] = ducks[j]>>i&1;

        for ( int j=0; j<K; j++ )
        {
            //  Spell 1
            for ( int k=0; k<n; k++ )
                if ( (spellOne[k]>>i&1)==0 )
                    T[j+1][k] += T[j][k]/2;
                else
                    T[j+1][k] += (1-T[j][k])/2;
            //  Spell 2
            for ( int k=0; k<n; k++ )
                T[j+1][spellTwo[k]] += T[j][k]/2;
        }

        ans += (1<<i)*T[K][0];
    }

    return ans;
}};