学步园

        水水更健康。。。。。最多30位，所以纯暴力都能过。题目：

描述

 大家都知道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

ac代码：

#include <stdio.h>
int f[300];
const int N=1314520;
int count_bit(int n){
	int r=0;
	while(n){
	  n>>=1;
	  r++;
	}
	return r;
}
int countone(int n){
	int r=0;
	while(n){
	  n&=(n-1);
	  r++;
	}
	return r;
}
int main(){
	freopen("1.txt","r",stdin);
	int n;
	f[0]=1;f[1]=1;f[2]=2;
	while(~scanf("%d",&n)){
      int sumdigit=count_bit(n);
	  int numone=countone(n);
	  int numzero=sumdigit-numone;
	  int x=numzero*numone;
	  for(int i=2;i<=x;++i){
	    f[i]=( ( f[i-1]%N ) + (f[i-2]%N) )%N;
	  }
	  printf("%d\n",f[x]);
	}
	return 0;
}