CF441E Valera and Number

有一个非常 naive 的想法，就是加操作使得末尾 \(0\) 变 \(1\)， \(1\) 变 \(0\)， \(\times 2\) 操作就是结尾 \(+\) 一个 \(0\)。
发现我们会遇到一个问题，就是进位，加操作会进位的！很烦。

发现 \(k\) 并不大，再思考思考，
诶，我们可以发现一个性质，只有 \(+k\) 以内的加法有可能对最终结果产生影响，原因也很简单就是 \(a\) 次 \(\times 2\) 操作之后，加法都要加 \(2^a\) 次才能产生影响，那么加法显然最多产生 \(+k\) 的影响。
记 \(f_{i,j}\) 表示 \(x+k\) 的二进制位数，那么我们就可以将加操作取缔，转移为 \(f_{i + 1,j – 1}\) \(+=(1-p) \times f_{i,j},\) \(f_{i+1,2j}\) \(+= p \times f_{i,j}\) 大于 \(k\) 的 \(j\) 不考虑即可。

Tips：
二进制 \(dp\) 如果位数不够用一定要考虑如何精简状态。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
using namespace std;
template <typename T> void read(T &n){ bool f = 1; char ch = getchar(); n = 0; for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 0; for (; isdigit(ch); ch = getchar()) n = (n << 1) + (n << 3) + (ch ^ 48); if (f == 0) n = -n;}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 210;
double p, f[N][N];
int x, k;

int main(){
	//FO("");
	read(x), read(k); int val;
	read(val);
	p = val / 100.0; 
	U(i, 0, k){
		// if ((x + i) & 1) continue ;
		for (int j = x + i; !(j & 1); j >>= 1) f[0][i]++;
	}

	U(i, 0, k - 1) U(j, 0, k) f[i + 1][j - 1] += (1 - p) * f[i][j], f[i + 1][min(k + 1, j * 2)] += p * (f[i][j] + 1);
	printf("%.7lf", f[k][0]); 
	return 0;
}

原文地址：http://www.cnblogs.com/SouthernWay/p/16871521.html