【日常学习】【高精】【数学递推】tyvj1375 山洞历险题解

我会带着你远行 2022-08-09 14:41 114阅读 0赞

**P1375** 山洞历险

时间: 1000ms / 空间: 131072KiB / Java类名: Main

## 描述 ##

小A在经历了和许多山头的一番大战后，总算拿到了最多的石子。他跌跌撞撞地来到了一个看上去比较隐蔽的山洞。让他惊奇的是，这个山洞里竟然摆满了美味佳肴，早已筋疲力尽饥肠辘辘的小A顺手抓了一个苹果咬了一口，他只觉得眼前一黑，便晕了过去……等他醒来时，发现自己被五花大绑，躺在一口大锅旁边。难道遇到了食人魔？小A大汗。  
    小A突然发现旁边的地上写着一行小字，“年轻人，恭喜你来到神奇山洞。如果你可以通过山洞，那么你将获得超人的rp，否则你将和很多人一样成为洞中的枯骨。按动你面前石锅左侧的按钮，它就可以随机变换图案，鲜花代表生机，骷髅则象征死亡，它们每次出现的可能性是相同的。如果连续两次出现鲜花，那你就可以挣脱绳子，通过山洞。”  
    小A的rp有限，在按动n次按钮后就会耗尽，如果此时他还未脱身，那他就over了。小A想请你帮忙计算当按了n次按钮时，他恰好能够脱身的几率。你能帮他吗？

## 输入格式 ##

一个正整数n

## 输出格式 ##

第一行，整数a，表示所求概率的分母  
    第二行，整数b，表示所求概率的分子

## 测试样例1 ##

### 输入 ###

> 2

### 输出 ###

> 4   
> 1

## 备注 ##

第一次是鲜花的概率为1/2，第二次还是鲜花的概率为1/2，两次概率相乘为1/4。  
对于30%的数据：n<=50  
对于100%的数据：n<=32767

这道题我推了一个多小时···血泪史啊···

然而如果写出来前十个（->鹏神@spiderKK做法），或者用DP做50内的小数据（->dafa@EVA-01做法） 就一目了然了 分子是fibonacci 分母是二的幂次方···

你或许会问：有的状态已经淘汰了，为什么种类还是二的幂次方？

事实上，就是这样的，我也不知道为什么，但是这就像七局五胜不可能七局都胜，但是概率情况总数还是要把它算在内···

我这里姑且提供一种可能可以理解的解释：有三种情况可以继续进入下一轮，一种被淘汰，那么未进入下一轮的概率为四分之一，这个四分之一包括了接下来未能扩展的所有状态。举个例子，如果下一轮每个状态扩展出两种状态，算上被淘汰的一共有八种，而实际有六种，这六种中如果有五个可以进入下一轮，那么进入第三轮的几率是(3/4)\*(5/6) 也就是在原来的三种中有六分之五，如果按四种就是八分之五。

晕了吗？现在我们回到最开始的时候，未进入第二轮的有四分之一，这里面包括了第二轮中的两个八分之一，因此如果把一开始就看做有八种情况，那么第一轮淘汰了两个八分之一，剩下六份；第二轮从这八分之六中淘汰八分之一，因此进入第三轮概率为5/8

好了，解释完毕，现在我们只要做一个高精递推和一个快速幂就可以了。fibonacci可以用三个数组做，只有高精加；如果有两个数组迭代也可以，b=a+b,a=b-a即可，但是要写高精减，而且可能出现退位和负数。

然而我们注意到可能要约分···这是很麻烦的问题，原本可以求gcd然后除法，但是高精取模和高精除都是噩梦啊···还好，分母二的幂次方只可能是儿的倍数，一个劲儿的除以二就可以了。只需要高精除单精···

然而中午一点的我眼看着时间不足，开始拖模板··1·无奈模板只有高精除高精，于是又拖了另一份带着二分优化的高精模板，拼凑修改，好容易过了····

就是不知道为什么，大于32767就爆···

事实上，数据并没有约分···

这是这道题目的代码：

#include 
       
          
    #include 
        
           
    #include 
         
            
    using namespace std;      
      
      
    const int power = 4;      //每次运算的位数为10的power次方，在这里定义为了方便程序实现  
    const int base = 10000;      //10的power次方。  
    const int MAXL = 4010;    //数组的长度。  
    
    int n;
    struct num  
    {  
        int a[MAXL];  
        num() { memset(a, 0, sizeof(a)); } 
        void add(int k) { if (k || a[0]) a[ ++a[0] ] = k; }     //在末尾添加一个数，除法的时候要用到  
        void re() { reverse(a+1, a+a[0]+1); }                   //把数反过来，除法的时候要用到  
        void print()                                            //打印此高精度数  
        {  
            printf("%d", a[ a[0] ]);        
            //先打印最高位，为了压位 或者 该高精度数为0 考虑  
            for (int i = a[0]-1;i > 0;--i)  
            printf("%0*d", power, a[i]);    
            //这里"%0*d", power的意思是，必须输出power位，不够则前面用0补足  
            printf("\n");  
        }  
    }p,q,ans,ax,bx,cx,ay,by,cy;  
      
      
    bool operator < (const num &p, const num &q)              //判断小于关系，除法的时候有用  
    {  
        if (p.a[0] < q.a[0]) return true;  
        if (p.a[0] > q.a[0]) return false;  
        for (int i = p.a[0];i > 0;--i)  
        {  
            if (p.a[i] != q.a[i]) return p.a[i] < q.a[i];  
        }  
        return false;  
    }  
      
      
    num operator + (const num &p, const num &q)               //加法，不用多说了吧，模拟一遍，很容易懂  
    {  
        num c;  
        c.a[0] = max(p.a[0], q.a[0]);  
        for (int i = 1;i <= c.a[0];++i)  
        {  
            c.a[i] += p.a[i] + q.a[i];  
            c.a[i+1] += c.a[i] / base;  
            c.a[i] %= base;  
        }  
        if (c.a[ c.a[0]+1 ]) ++c.a[0];  
        return c;  
    }  
      
      
    num operator - (const num &p, const num &q)               //减法，也不用多说，模拟一遍，很容易懂  
    {  
        num c = p;  
        for (int i = 1;i <= c.a[0];++i)  
        {  
            c.a[i] -= q.a[i];  
            if (c.a[i] < 0) { c.a[i] += base; --c.a[i+1]; }  
        }  
        while (c.a[0] > 0 && !c.a[ c.a[0] ]) --c.a[0];            
        //我的习惯是如果该数为0，那么他的长度也是0，方便比较大小和在末尾添加数时的判断。  
        return c;  
    }  
      
      
    num operator * (const num &p, const num &q)                   
    //乘法，还是模拟一遍。。其实高精度就是模拟人工四则运算！  
    {  
        num c;  
        c.a[0] = p.a[0]+q.a[0]-1;  
        for (int i = 1;i <= p.a[0];++i)  
        for (int j = 1;j <= q.a[0];++j)  
        {  
            c.a[i+j-1] += p.a[i]*q.a[j];  
            c.a[i+j] += c.a[i+j-1] / base;  
            c.a[i+j-1] %= base;  
        }  
        if (c.a[ c.a[0]+1 ]) ++c.a[0];  
        return c;  
    }  
      
    num operator / (const num &p, const int &b)               //高精除单精 加入了二分优化 
    {  
        num ret;  
        int i,down = 0;   
         for(i = p.a[0] ; i >= 1 ; i--)
         { 
             ret.a[i] = (p.a[i] + down * (base)) / b; 
             down = p.a[i] + down * (base) - ret.a[i] * b; 
        } 
        ret.a[0] = p.a[0]; 
        while (ret.a[0] > 0 && !ret.a[ret.a[0]]) --ret.a[0];  
        return ret; 
    } 
      
    
    num operator / (const num &p, const num &q)               //除法，这里我稍微讲解一下  
    {  
        num x, y;  
        for (int i = p.a[0];i >= 1;--i)                       //从最高位开始取数  
        {  
            y.add(p.a[i]);             //把数添到末尾（最低位），这时候是高位在前，低位在后  
            y.re();                    //把数反过来，变为统一的存储方式：低位在前，高位在后  
            while ( !(y < q) )         //大于等于除数的时候，如果小于的话，其实答案上的该位就是初始的“0”  
                y = y - q, ++x.a[i];   //看能减几个除数，减几次，答案上该位就加几次。  
            y.re();                    //将数反过来，为下一次添数做准备  
        }  
        x.a[0] = p.a[0];  
        while (x.a[0] > 0 && !x.a[x.a[0]]) --x.a[0];  
        return x;  
    }    
    
      
    int main()  
    {  
        freopen("cave.in","r",stdin);
        freopen("cave.out","w",stdout);
        scanf("%d",&n);//x为分子，跑fibonacci y是分母，跑快速幂  
        ax.a[0]=bx.a[0]=1;
        ax.a[1]=bx.a[1]=1;
        if (n<4)
    	{
            if (n==2) printf("4\n1\n");
    		if (n==3) printf("8\n1\n"); 
    		return 0;
    	}
        for (int i=4;i<=n;i++)
        {
        	cx=ax+bx;
        	ax=bx;
        	bx=cx;
    	}
    	ay.a[0]=1;
    	ay.a[1]=2;
    	by.a[0]=1;
    	by.a[1]=1;
    	int b=n;
    	while (b)//by is ans
    	{
    		if (b&1==1) by=by*ay;
    		ay=ay*ay;
    		b>>=1;
    	}
        while (cx.a[1]%2==0)
        {
        	cx=cx/2;
        	by=by/2;
    	}
    	by.print();
    	cx.print();
    	return 0;
    }  
    
    /* 
    
    while (b)
    {
        if (b & 1 == 1) ans*=a;
        a*=a;
        b>>=1;
    } 
    
    */
    
    
    /*
    BigNum BigNum::operator/(const int & b) const   //大数对一个整数进行相除运算
    218 { 
    219     BigNum ret; 
    220     int i,down = 0;   
    221     for(i = len - 1 ; i >= 0 ; i--)
    222     { 
    223         ret.a[i] = (a[i] + down * (MAXN + 1)) / b; 
    224         down = a[i] + down * (MAXN + 1) - ret.a[i] * b; 
    225     } 
    226     ret.len = len; 
    227     while(ret.a[ret.len - 1] == 0 && ret.len > 1)
    228         ret.len--; 
    229     return ret; 
    230 }
    */
    
    
    /*
    //cave
    //copyright by ametake
    #include
          
           
    #include
           
             #include
            
              #define ll long long using namespace std; const int maxn=40000+10; ll a[maxn],b[maxn],enb[maxn],k; ll x=1,y=1; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } void yue(ll &x,ll &y) { ll g=gcd(x,y); x/=g; y/=g; } void cal(int m) { a[2]=3; a[1]=2; b[2]=4; b[1]=2; enb[1]=1; enb[2]=2; for (int i=3;i<=m;i++) { enb[i]=enb[i-1]+enb[i-2]; b[i]=b[i-1]+b[i-2]; a[i]=a[i-1]+a[i-2]; } a[m]-=enb[m]; for (int i=2;i<=m;i++) { x*=a[i]; y*=b[i]; yue(x,y); } } int main() { //freopen("2.txt","w",stdout); scanf("%lld",&k); if (k<3) { if (k==2) printf("4\n1\n"); else printf("0\n"); return 0; } cal(k-1);//先写普京，再考虑是否改高精 for (int i=1;i

尽管如此 高精还是要自己好好学写出来

——冰雪林中著此身，不同桃李混芳尘