题目描述

有一个随机数字生成函数，对于一个输入X，有A/100的概率生成 X AND K，有B/100的概率生成 X OR K ，有C/100的概率生成 X XOR K 。 0 ≤ X, K ≤ 10^9，0 ≤ A, B, C ≤ 100，A+B+C = 100。 现在假设有N个这样的随机数字生成函数，问最后输出数字的期望值。

思路

对于数字二进制下的每一位只有两种状态0或者1，同时每一位相互独立，所以可以分开考虑每一位，就算出经过N步之后每一位为1的概率，则最后的期望可以表示为：$ expect = \sum_{j=0}^{31} {p_j * (1 « j)} $ ，$p_j$表示经过N步随机数字生成函数后第j位为1的概率。

所以，有DP：
令dp[i][j][s]表示经过i步随机数字生成函数后第j位状态为s的概率，s = 0 / 1，有状态转移方程：
If (k & (1 << j)) > 0 :
dp[i][j][0] += dp[i-1][j][0] * a / 100
dp[i][j][0] += dp[i-1][j][1] * c / 100
dp[i][j][1] += dp[i-1][j][1] * a / 100
dp[i][j][1] += dp[i-1][j][0] * b / 100
dp[i][j][1] += dp[i-1][j][1] * b / 100
dp[i][j][1] += dp[i-1][j][0] * c / 100
Else :
dp[i][j][0] += dp[i-1][j][0] * a / 100
dp[i][j][0] += dp[i-1][j][1] * a / 100
dp[i][j][0] += dp[i-1][j][0] * b / 100
dp[i][j][0] += dp[i-1][j][0] * c / 100
dp[i][j][1] += dp[i-1][j][1] * b / 100
dp[i][j][1] += dp[i-1][j][1] * c / 100

初始化，则根据X的每一位0或者1，对dp[0][j][0]和dp[0][j][1]赋值1或者0。

代码

#include <bits/stdc++.h>
using namespace std;

#define clr(x,c) memset(x, c, sizeof(x))
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define psi pair<string, int>
#define inf 0x3f3f3f3f
typedef long long lld;

const int N = 111111;
const int M = 31; // x & k >= 0, bit(31) = 0

double dp[N][M][2];

double solve()
{
   double ret = 0.0;
   int n, x, k, a, b, c;
   cin >> n >> x >> k >> a >> b >> c;

   // init
   clr(dp, 0);
   for (int j = 0; j < M; ++j) {
       if ( x & (1 << j) ) {
           dp[0][j][0] = 0.0;
           dp[0][j][1] = 1.0;
       } else {
           dp[0][j][0] = 1.0;
           dp[0][j][1] = 0.0;
       }
   }

   // dp
   for (int j = 0; j < M; ++j) {
       for (int i = 1; i <= n; ++i) {
           if ( k & (1 << j) ) {
               dp[i][j][0] += dp[i-1][j][0] * a / 100;
               dp[i][j][0] += dp[i-1][j][1] * c / 100;
               dp[i][j][1] += dp[i-1][j][1] * a / 100;
               dp[i][j][1] += (dp[i-1][j][0] + dp[i-1][j][1]) * b / 100;
               dp[i][j][1] += dp[i-1][j][0] * c / 100;
           } else {
               dp[i][j][0] += (dp[i-1][j][0] + dp[i-1][j][1]) * a / 100;
               dp[i][j][0] += dp[i-1][j][0] * b / 100;
               dp[i][j][0] += dp[i-1][j][0] * c / 100;
               dp[i][j][1] += dp[i-1][j][1] * b / 100;
               dp[i][j][1] += dp[i-1][j][1] * c / 100;
           }
       }
       ret += dp[n][j][1] * (1 << j);
   }

   return ret;
}

int main ()
{
   freopen("F:/#test-data/in.txt", "r", stdin);
   freopen("F:/#test-data/out.txt", "w", stdout);
   ios::sync_with_stdio(false); cin.tie(0);
   cout << fixed << showpoint;
   int t; cin >> t;
   for (int cas = 1; cas <= t; ++cas) {
       cout << "Case #" << cas << ": ";
       cout << setprecision(9) << solve() << endl;
   }
   return 0;
}