[CodeForces-441E]Valera and Number

题目大意：
　　给你一个数x，进行k次操作：
　　1.有p%的概率将x翻倍；
　　2.有1-p%的概率将x加1。
　　问最后二进制下x末尾0个数的期望。

思路：
　　动态规划。
　　由于k只到200，所以每次修改只与最后8位有关。
　　f[i][x][y][z]表示操作次数为i时，末尾8为表示的数字为x，第9位为y，第9位及以上和第9位数字连续相同的长度。
　　对于两种情况分别转移，注意特判超过8位的进位。
　　最后计算期望的时候，可以枚举第一维为k的所有状态，然后通过状态可以直接计算出末尾0的数量，乘上概率即可。

 #include<cstdio>

 #include<cctype>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int K=;

 double f[K][][][];//[処理回数][末尾8bit][9bit目の値][9bit目の値が上にいくつ連続するか]

 int main() {

     int x=getint(),k=getint();

     double p=getint()/100.0;

     //初始状态

     int cnt=,tmp=x>>;

     while(tmp&&((tmp&)==((x>>)&))) {

         tmp>>=;

         cnt++;

     }

     f[][x&][(x>>)&][cnt]=;

     for(register int i=;i<k;i++) {

         for(register int x=;x<=;x++) {

             for(register int y=;y<;y++) {

                 for(register int z=;z<;z++) {

                     /*times 2*/

                     f[i+][(x<<)&][(x>>)&][(((x>>)&)^y)?:(z+)]+=f[i][x][y][z]*p;

                     /*plus 1*/

                     if(x==) {//特殊情况：考虑最后八位存不下而进位的情况

                         if(y) {//如果第九位是1，则相当于前面那么多1都变成0

                             f[i+][][][z]+=f[i][x][y][z]*(-p);

                         } else {//如果第九位是0，则相当于把这个0变成1

                             f[i+][][][]+=f[i][x][y][z]*(-p);//这里把9位以后的1算作多少都没关系，因为反正最后统计的是0

                         }

                     } else {

                         f[i+][x+][y][z]+=f[i][x][y][z]*(-p);

                     }

                 }

             }

         }

     }

     //计算期望

     double ans=;

     for(register int x=;x<=;x++) {

         for(register int y=;y<;y++) {

             for(register int z=;z<;z++) {

                 int cnt=,tmp=x;

                 while(cnt<&&!(tmp&)) {

                     cnt++;

                     tmp>>=;

                 }

                 if(!y&&cnt==) cnt+=z;

                 ans+=f[k][x][y][z]*cnt;

             }

         }

     }

     printf("%.13f\n",ans);

     return ;

 }

巴特西

[CodeForces-441E]Valera and Number

最新文章

热门文章