3322 时空跳跃者的困境

时间限制: 1 s

空间限制: 64000 KB

题目等级 : 钻石 Diamond

题目描述 Description

背景：收集完能量的圣殿战士suntian开始了他的追捕行动。费尽千辛万苦，他终于看到了飞翔的影子，于是他加快了速度冲向飞翔。在两人只差0.01mm的时候，飞翔突然手一挥，在suntian眼前就出现了一个黑洞。suntian掉入其中……

描述：等suntian站稳后，发现出现了一个扭曲的三维时空，于是suntian用心灵波动在0.00000000001ms内找到了这个时空的奇点(就是出口)。他发现奇点是闭合的，然而这个奇点的旁边竟然有一个开关(飞翔的失误？！)，而且是手摇转动的！suntian来到开关前，发现在开关的把手上有一些文字：“To open this point,turn “s” times.If turn the wrong times,this point will disappear.”但是这个s又是多少呢？于是suntian开始在开关附近寻找。终于，suntian发现了一块大石板，上面刻着：s可由一系列二项式系数（二项式的展开是按照二项式的标准展开方式展开的）组成的三角形数阵推得。这个三角形数阵的第k行就是(a+b)^(k-1)的展开式的二项式系数(k从1开始)。s=第n行的第一个数+第n-1行的第二个数+第n-2行的第三个数+…(直到要加的某一个数已经不属于这个三角形)。那么，suntian到底要转动多少下呢？

输入描述 Input Description

共一行，为n，(1<=n<=10^4,n∈N)。

输出描述 Output Description

输出：共一行，为总转动数s。

样例输入 Sample Input

5

样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

请看上面。

分类标签 Tags

数学/物理 矩阵乘法 数论

/*没分做法 但是方法很重要2333.组合数 二项式定理乱搞.可以推出C(n,m-1)和C(n-1,m)的关系.然后 然后 然后无意间试前几项发现竟是个斐波那契数列....论数学题暴力的作用.O(n)的 只是爆了精度.这种方法不改高精度了 涉及除法.正确做法就是斐波那契数列+高精度加法了先不打了.so我会用别的方法算斐波那契数列了23333.(然而并没有什么卵用.*/#include
    
     #include
     
      #define LL long long#define MAXN 10001using namespace std;LL ans,c[MAXN],n,m,i,j;void slove(){    c[0]=1;    //for(int i=1;i<=m;i++) c[i]=c[i-1]*(n-i+1)/i;    //ans=c[m];    ans=c[1]=1;i=n,j=1;    for(int k=2;k<=m;k++)    {        c[k]=c[k-1]*((i-j)*(i-j+1))/(i*j);        i--,j++;        ans+=c[k];    }    cout<
      
       >n;n--;    if(n&1) m=(n>>1)+1;    else m=(n>>1)+1;    slove();    return 0;}