首页 > 代码库 > FZOJ 1640 place blocks
FZOJ 1640 place blocks
OJ题目 : click here ~~
题目分析:转自
不知道为什么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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。