A-A+

AC_mm玩dota

2012年08月16日 acm水题 暂无评论 阅读 25 次

AC_mm玩dota

时间限制:1000 ms  |  内存限制:65535 KB
难度:2
描述

 大家都知道AC_mm比较喜欢玩游戏,特别是擅长war3这款经典游戏。某天AC_mm来到了VS平台上 ,准备去虐菜鸟,正巧一个不小心将我们ACM队长虐了 ^_^,我们的队长这下可不高兴了,说要出一道难题让AC_mm难堪一下。题目描述是这样的,给一个正整数n,n在二进制表示的情况下(不含前导0和符号位)有a个1和b个0,求斐波拉契数列的第a*b项对1314520取模后的值ans。

                                                                 注意(斐波拉契数列: f[0]=1,f[1]=1; f[n]=f[n-1]+f[n-2] ; n>=2;)

输入
输入:有多组测试数据,输入一个正整数n(n<1000000000);
输出
输出:ans的值
样例输入
12
6
样例输出
5
2

解题思路:看不出和dota毛关系~~,移位求二进制,很快就能解出!
[cpp]

#include <iostream>
using namespace std;
int main()
{
int i,a,b,z;
long long n,f[255]={1,1};
while(cin>>n)
{
a=z=0;
for(i=31;i>=0;i--)
{
if(n>>i&1) a++;
if(a) z++;
}
b=z-a;
for(i=2;i<=a*b;i++)
{
f[i]=f[i-2]+f[i-1];
f[i]%=1314520;
}
cout<<f[i-1]<<endl;
}
return 0;
}

[/cpp]

标签:

给我留言

Copyright © C/C++程序员之家 保留所有权利.   Theme  Ality 浙ICP备15011757号-3

用户登录