首页 > 代码库 > NYOJ 527 AC_mm玩dota

NYOJ 527 AC_mm玩dota

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

本题思路简单,关键在于取二进制,转换,得出x*y,打表时取余。

#include<cstdio>
int a[260];
int s[40];
int shift1(int n)
{
	int num=1,i;
	s[0]=n%2;
	while(n/2!=0){
		n/=2;
		s[num++]=n%2;
	}
	int t;
	for(i=0;i<=num/2;i++)//这里num/2别写成num了
	{
		t=s[i];
		s[i]=s[num-1-i];
		s[num-1-i]=t;
	}
	
	int x=0,y=0;
	for(i=0;i<num;i++)
		if(s[i]==1)x++;
		y=num-x;
		return x*y;
}
int main()
{
	int n;
	a[0]=1,a[1]=1;
	for(int i=2;i<240;i++)
		a[i]=(a[i-1]+a[i-2])%1314520;
	while(~scanf("%d",&n)){
		printf("%d\n",a[shift1(n)]);
	}
	return 0;
}

NYOJ上面的后台数据库肯定有问题,不在打表时取余也可以过!!!

NYOJ 527 AC_mm玩dota