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

[CEOI2015 Day2] 世界冰球锦标赛

题目描述

译自 CEOI2015 Day2 T1「Ice Hockey World Championship

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

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

输入格式

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

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

输出格式

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

5 1000
100 1500 500 500 1000
8

提示

样例解释

八种方案分别是:

  • 一场都不看,溜了溜了
  • 价格 100100 的比赛
  • 第一场价格 500500 的比赛
  • 第二场价格 500500 的比赛
  • 价格 100100 的比赛和第一场价格 500500 的比赛
  • 价格 100100 的比赛和第二场价格 500500 的比赛
  • 两场价格 500500 的比赛
  • 价格 10001000 的比赛

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

数据组号 121-2 343-4 575-7 8108-10
NN \leq 1010 2020 4040
MM \leq 10610^6 101810^{18} 10610^6 101810^{18}