Time Limit: 10 Sec  Memory Limit: 512 MBSec  Special Judge

Submit: 215  Solved: 112

Description

Input

Output

Sample Input

3 0.5

Sample Output

2.000000

HINT

 

1<=N<=10^18

 

Source

 

加密和不加密各自是独立问题

后者是炒鸡麻烦的数位DP

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define LL long long 6 using namespace std; 7 const int mxn=100010; 8 LL n; 9 LL b[70];10 double p;11 int len;12 double pw(){
   //加密 13     double res=0;14     for(int i=0;i
         
          >i)&1)f[i]=f[i-1]+(double)b[i]/(n+1)*b[i]*2+(double)(b[i]-1)*1.0/(n+1)*b[i];35         else f[i]=f[i-1]*2+(b[i])/(double)(n+1)*(b[i]);36     }37     for(int i=len-1;i>=0;i--){38         if((n>>i)&1){
   //x可以取1 39             if((m>>i)&1){
   //y可以取1 40                 res+=(b[i+1]-1)*(double)(m+1-(b[i]))/(n+1);41                 m=(b[i])-1;42             }43             res+=b[i]*(double)(m+1)/(n+1);44         }45         else{46             if((m>>i)&1){47                 res+=(b[i])*(double)(m+1-(b[i]))/(n+1);48                 m^=(b[i]);49                 res+=i-1>=0?f[i-1]:0;50             }51         }52     }53     n++;54     return res;55 }56 int main(){57     int i,j;58     scanf("%lld%lf",&n,&p);59     len=1;60     while((1LL<
          
           <=n)++len;61 for(i=0;i<=len;i++)b[i]=1LL<