P4799 [CEOI2015 Day2]世界冰球锦标赛

    • 245通过
    • 673提交
  • 题目提供者 alpha1022
  • 评测方式 云端评测
  • 标签 搜索 概率论,统计 背包 2015 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    译自 CEOI2015 Day2 T1「Ice Hockey World Championship

    今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格,他不是任何团队的粉丝,也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱,他会去看所有的比赛。不幸的是,他的财产十分有限,他决定把所有财产都用来买门票。

    给出 Bobek 的预算和每场比赛的票价,试求:如果总票价不超过预算,他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看,则认为这两种方案不同。

    输入输出格式

    输入格式:

    第一行,两个正整数 $N$ 和 $M(1 \leq N \leq 40,1 \leq M \leq 10^{18})$,表示比赛的个数和 Bobek 那家徒四壁的财产。

    第二行,$N$ 个以空格分隔的正整数,均不超过 $10^{16}$,代表每场比赛门票的价格。

    输出格式:

    输出一行,表示方案的个数。由于 $N$ 十分大,注意:答案 $\le 2^{40}$。

    输入输出样例

    输入样例#1: 复制
    5 1000
    100 1500 500 500 1000
    输出样例#1: 复制
    8

    说明

    样例解释

    八种方案分别是:

    • 一场都不看,溜了溜了
    • 价格 $100$ 的比赛
    • 第一场价格 $500$ 的比赛
    • 第二场价格 $500$ 的比赛
    • 价格 $100$ 的比赛和第一场价格 $500$ 的比赛
    • 价格 $100$ 的比赛和第二场价格 $500$ 的比赛
    • 两场价格 $500$ 的比赛
    • 价格 $1000$ 的比赛

    有十组数据,每通过一组数据你可以获得 10 分。各组数据的数据范围如下表所示:

    数据组号 $1-2$ $3-4$ $5-7$ $8-10$
    $N \leq$ $10$ $20$ $40$ $40$
    $M \leq$ $10^6$ $10^{18}$ $10^6$ $10^{18}$
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。