Valera and Number

Time Limit: 20 Sec Memory Limit: 512 MB

Description

img

Input

img

Output

img

Sample Input

5 3 25

Sample Output

1.9218750000

HINT

img

Solution

考虑运用DP。

img

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 800005;
const int MOD = 1e9 + 7;
const int all = 255;

int x, n;
double p;
double f[205][260][255][2];
double Ans;
int val, num;

int get()
{
    int res;char c;
    while( (c=getchar())<48 || c>57 );
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res;
}

void Deal_first(int n)
{
    int record[250], num = 0, x = n;
    while(x)
        record[++num] = x & 1,
    x >>= 1;
    int j = 1, pos = 9, val = record[pos];
    for(pos = 9; pos + j - 1 <= num; j++)
        if(record[pos + j] != val) break;

    f[0][n & all][j][val] = 1;
}

int Get(int x)
{
    int res = 0;
    while(x % 2 == 0) res++, x >>= 1;
    return res;
}

int main()
{
    x = get(), n = get(), p = (double)get() / 100;
    Deal_first(x);

    for(int i = 0; i < n; i++)
        for(int s = 0; s <= all; s++)
            for(int j = 1; j <= 250; j++)
                for(int k = 0; k <= 1; k++)
                {
                    val = s >> 8 - 1 & 1;
                    if(val != k) num = 1; else num = j + 1;
                    f[i + 1][s << 1 & all][num][val] += f[i][s][j][k] * p;

                    val = s == all ? (k ^ 1) : k;
                    if(val != k && k == 0) num = 1; else num = j;
                    f[i + 1][s + 1 & all][num][val] += f[i][s][j][k] * (1 - p);
                }

    for(int s = 0; s <= all; s++)
        for(int j = 1; j <= 250; j++)
            for(int k = 0; k <= 1; k++)
            {
                if(s == 0 && k == 0) val = j + 8;
                else if(s == 0 && k == 1) val = 8;
                else val = Get(s);
                Ans += f[n][s][j][k] * val;
            }

    printf("%.8lf", Ans);
}