Codeforces 441E Valera and Number dp

谁借莪１个温暖的怀抱￠ 2021-12-17 00:17 221阅读 0赞

[Valera and Number][]

感觉想了挺久的。。

dp\[ o \]\[ i \]\[ mask \] ， 其中mask表示最后9位是什么。

如果mask == 0  ， 表示进行了o轮， 当前lowbit是哪位这种状态的概率。

如果mask != 0 ， 表示进行了o轮， 最后9位为mask， 从第10位开始连续多少个1这种状态的概率。

从dp\[ o \]\[ i \]\[ 0 \] 经过 +1 这种操作的时候就可以舍弃掉 i ， 因为这些连续的1已经没有用了， 即使后面全部是+1也加不到这位。

#include<bits/stdc++.h>
    #define LL long long
    #define LD long double
    #define ull unsigned long long
    #define fi first
    #define se second
    #define mk make_pair
    #define PLL pair<LL, LL>
    #define PLI pair<LL, int>
    #define PII pair<int, int>
    #define SZ(x) ((int)x.size())
    #define ALL(x) (x).begin(), (x).end()
    #define fio ios::sync_with_stdio(false); cin.tie(0);
    
    using namespace std;
    
    const int N = 250 + 7;
    const int inf = 0x3f3f3f3f;
    const LL INF = 0x3f3f3f3f3f3f3f3f;
    const int mod = 1e9 + 7;
    const double eps = 1e-10;
    const double PI = acos(-1);
    
    template<class T, class S> inline void add(T &a, S b) {a += b; if(a >= mod) a -= mod;}
    template<class T, class S> inline void sub(T &a, S b) {a -= b; if(a < 0) a += mod;}
    template<class T, class S> inline bool chkmax(T &a, S b) {
        return a < b ? a = b, true : false;}
    template<class T, class S> inline bool chkmin(T &a, S b) {
        return a > b ? a = b, true : false;}
    
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
    int x, k, p;
    double dp[2][250][1 << 9];
    double p1, p2;
    
    double (*f)[1 << 9] = dp[0];
    double (*g)[1 << 9] = dp[1];
    
    inline int getLow(int mask) {
        for(int i = 0; ; i++) if(mask >> i & 1) return i;
    }
    
    int main() {
        scanf("%d%d%d", &x, &k, &p);
        p1 = 1.0 * p / 100;
        p2 = 1 - p1;
    
        int c = 0, mask = (x & 511);
    
        if(mask) {
            for(int i = 9; ; i++) {
                if(x >> i & 1) c++;
                else break;
            }
        } else {
            c = getLow(x);
        }
    
        f[c][mask] = 1;
    
        for(int o = 0; o < k; o++) {
            swap(f, g);
            for(int i = 0; i <= 240; i++)
                for(int mask = 0; mask < (1 << 9); mask++)
                    f[i][mask] = 0;
            for(int i = 0; i < 240; i++) {
                for(int mask = 0; mask < (1 << 9); mask++) {
                    if(mask) {
                        // +1
                        if(mask + 1 == (1 << 9)) {
                            f[i + 9][0] += g[i][mask] * p2;
                        } else {
                            f[i][mask + 1] += g[i][mask] * p2;
                        }
    
                        // *2
    
                        int nmask = (mask << 1) & 511;
                        int bit = mask >> 8 & 1;
    
                        if(nmask) {
                            if(bit) {
                                f[i + 1][nmask] += g[i][mask] * p1;
                            } else {
                                f[0][nmask] += g[i][mask] * p1;
                            }
                        } else {
                            f[9][0] += g[i][mask] * p1;
                        }
    
                    } else {
                        // +1
                        f[0][1] += g[i][mask] * p2;
                        // *2
                        f[i + 1][0] += g[i][mask] * p1;
                    }
                }
            }
        }
    
        double ans = 0;
    
        for(int i = 0; i <= 240; i++) {
            for(int mask = 0; mask < (1 << 9); mask++) {
                if(mask) {
                    ans += getLow(mask) * f[i][mask];
                } else {
                    ans += i * f[i][mask];
                }
            }
        }
    
        printf("%.12f\n", ans);
        return 0;
    }
    
    /*
    */

转载于:https://www.cnblogs.com/CJLHY/p/11114448.html

[Valera and Number]: https://codeforces.com/problemset/problem/441/E