若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1018: Give me the answer

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,371

题目描述

Farmer John commanded his cows to search for different sets of numbers that sum to a given number.
The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that
sum to 7:
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4
Help FJ count all possible representations for a given integer N (1 <= N <= 1 ,000,000)

输入

The first line of the input contains the number of test cases in the file. And t he first line of each case
contains one integer numbers n

输出

For each test case, output a line with the ans % 1000000000.

样例输入

1
7

样例输出

6

参考代码

#include<stdio.h>
#define MAX 1000010
int a[MAX];
int main() 
{
    int n, m, i;
    a[1] = 1;
    a[2] = 2;
    for (i = 3; i <= MAX; ++i) 
    {
        if(i & 1)
                    a[i] = a[i - 1] % 1000000000; else
                    a[i] = (a[i - 1] + a[i / 2]) % 1000000000;
    }
    scanf("%d", &n);
    while(n--) 
    {
        scanf("%d", &m);
        printf("%dn", a[m]);
    }
    return 0;
}

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Skip 原站点 Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist