首页 > 代码库 > FZOJ 1640 place blocks

FZOJ 1640 place blocks

OJ题目 : click here ~~

题目分析:转自

sentimental_man的博客 

不知道为什么csdn不让给出这篇博文的网址,只能这样啦,感谢原作者的辛勤劳动。下面都是来自这篇博文。

1.对于本题的递推式很简单 f[i]=2*f[i-2]+f[i-1]

2.本题有个地方很奇怪就是最后结果要对2^64取余,这样的就无法一边算一边取余,因为会越界,也不太可能用高精度

3.那该怎么做呢?因为是对2^64(1<<64)取余,所以我们先把前几项算出来的结果看看:

          f[i]    二进制
i=1         1          1
i=2         3         11
i=3         5        101
i=4         11      1011
i=5         21     10101
i=6         43    101011
i=7         85   1010101

……       ……     ……

发现什么没有,二进制的位数等于i的值,对于所有的f[i]值前缀都是1和0交替(除了最后两位)
如果i是奇数:最后两位为01;
如果i是偶数:最后两位为11;

当i是63的时候为 1010101……01
当i是64的时候为 1010101……11
此时取余的结果还都是他们本身。

当i大于64时候,取余的结果就是把从右往左数大于64的位全部去掉,保留低64位。根据上面的规律
很容易知道单i是奇数时,f[i]=f[63] 当i是偶数时f[i]=f[64] (i>64)


AC_CODE

typedef unsigned long long  LL ;
const int Max_N = 65;
LL F[Max_N];
int main()
{
    int N;
    int i , j , k;
    F[1] = 1;
    F[2] = 3;
    for(i = 3;i <= Max_N;i++){
        F[i] = 2 * F[i - 2] + F[i - 1];
    }
    while(scanf("%d",&N) != EOF){
        if(N <= 64) printf("%I64u\n",F[N]);
        else printf("%I64u\n",F[63 + (N + 1)%2]);
    }
    return 0;
}