首页 > 其他 > 详细

HDU-5363 Key Set

时间:2015-08-07 10:56:38      阅读:218      评论:0      收藏:0      [点我收藏+]

http://acm.hdu.edu.cn/showproblem.php?pid=5363

Key Set

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 355 Accepted Submission(s): 233


Problem Description
soda has a set S技术分享 with n技术分享 integers {1,2,,n}技术分享 . A set is called key set if the sum of integers in the set is an even number. He wants to know how many nonempty subsets of S技术分享 are key set.
 

 

Input
There are multiple test cases. The first line of input contains an integer T技术分享 (1T10技术分享5技术分享)技术分享 , indicating the number of test cases. For each test case:

The first line contains an integer n技术分享 (1n10技术分享9技术分享)技术分享 , the number of integers in the set.
 

 

Output
For each test case, output the number of key sets modulo 1000000007.
 

 

Sample Input
4 1 2 3 4
 

 

Sample Output
0 1 3 7
 

 

Source
一个(1-n)集合的子集的和是偶数的个数
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
#define MOD 1000000007
long long ksm(long long x,long long n)
{
    long long pw = 1;
    while (n > 0)
    {
        if (n & 1)        // n & 1 等价于 (n % 2) == 1
            pw =(pw*x+MOD)%MOD;
        x =(x*x+MOD)%MOD;
        n >>= 1;        // n >>= 1 等价于 n /= 2
    }

    return pw;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long n;
        scanf("%lld",&n);
        n=n-1;
        printf("%lld\n",ksm(2,n)-1);
    }
    return 0;
}

 

 

HDU-5363 Key Set

原文:http://www.cnblogs.com/cancangood/p/4710022.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!