原 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层,速度还是很快的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

tensorflow读取数据-tfrecord格式

概述关于tensorflow读取数据,官网给出了三种方法: 1、供给数据:在tensorflow程序运行的每一步,让python代码来供给数据 2、从文件读取数...

1.1K6
来自专栏数据结构与算法

3002 石子归并 3

 时间限制: 1 s  空间限制: 256000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 有n堆石子...

3477
来自专栏数据结构与算法

BZOJ3624: [Apio2008]免费道路(最小生成树)

这棵树上有一些0边是必须要选的,我们先把他们找出来,如果数量$\geqslant k$显然无解

933
来自专栏大闲人柴毛毛

贪心算法(三)——最佳合并模式

问题描述 给定n个有序文件,每个文件的记录数分别为w1~wn,请给出一种两两合并的方案,使得总合并次数最少。 注意: 1. 外排序算法是将多个有序文件合...

42210
来自专栏数据结构与算法

09:LGTB 学分块

总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB描述 LGTB 最近在学分块,但是他太菜了,分的块数量太多他就混乱...

3517
来自专栏WOLFRAM

Mma粉丝分享:全国建模大赛B题椭圆形活动桌面设计

1463
来自专栏小樱的经验随笔

BZOJ 1293: [SCOI2009]生日礼物【单调队列】

1293: [SCOI2009]生日礼物 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2534  Solv...

2625
来自专栏菩提树下的杨过

VisualTreeHelper

Silverlight中只有可视化树,没有WPF中的逻辑树,这一点可从SL的sdk文档中得到印证: 可视化树概念也存在于 WPF 中,它与 Silverligh...

2357
来自专栏WOLFRAM

交互式查询化学键信息

2513
来自专栏数据结构与算法

洛谷P2252 取石子游戏(威佐夫博弈)

题目背景 无 题目描述 有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是...

4617

扫码关注云+社区

领取腾讯云代金券