原 2015 Multi-Universi

1011.Key Set

Summary

For a given set {1, 2, . . . , nn}, you are to find the number of nonempty subsets with even sum.

Solution

Let aa be the number of even integers and bb be the number of even integers. The answer is:

2^{a}(\begin{pmatrix}b\0 \end{pmatrix}+\begin{pmatrix}b\2 \end{pmatrix}+2a((b0)+(b2)+…)=2^{a+b-1}=2^{n-1}-1)=2a+b−1=2n−1−1

Time complexity: O(log\ n)O(log n)

----------------------大家好我是分割线------------------------

    作为一支酱油队，我们不负众望的只做出了水题（1011）。下面附上代码：

#include <stdio.h>
#include <iostream>
#define NUM 1000000007
using namespace std;

long long d[10000000];

long long def(int n)
{
    if(n<10000000)
    {
        return d[n];
    }
    return (def(n/2)*def(n-n/2))%NUM;
}

int main()
{
    long long n;
    int t;

    d[0]=1;
    for(int i=1;i<10000000;i++)
    {
        d[i]=(d[i-1]*2)%NUM;
    }

    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&n);
        long long ans = def(n-1)-1;
        printf("%lld\n",ans);
    }
    return 0;
}

    我们做着做着，突然发现如何快速得到2的n次方似乎是个问题，又不能开出10^9大小的数组，所以干脆开了个10^8大小的数组保存2^i，当所给的n大于10^8时，二分即可。递归树只有5层，速度还是很快的。