#3367. 「IOI2020」装饼干

内存限制:1024 MiB 时间限制:1000 ms 题目类型:交互
上传者: PinkRabbit

题目描述

注意:在 LibreOJ 上,由于语言限制,目前只支持以下语言的提交:

  • C++ 11
  • C++ 11 (Clang)
  • C++ 11 (NOI)
  • C++ 17
  • C++ 17 (Clang)

Khong 阿姨在组织一场有 x 位选手参加的竞赛,她打算给每位选手一袋饼干。总共有 k 种不同类型的饼干,编号为从 0 k - 1 。类型为 i 0 \le i \le k - 1 )的每块饼干都有一个口味值 2^i 。在 Khong 阿姨的食品储藏室里,有 a_i (有可能为 0 )块类型为 i 的饼干。

对每种类型的饼干,Khong 阿姨在每个袋子都会装上 0 或者多块。所有袋子里面类型为 i 的饼干的总块数不能超过 a_i 。一个袋子里面所有饼干的口味值的总和,被称为这袋饼干的总口味值

请帮 Khong 阿姨算一下,究竟存在多少不同的 y 值,使得她可以装出 x 袋饼干,而且每袋饼干的总口味值都等于 y

实现细节

你需要实现以下函数:

long long count_tastiness(long long x, std::vector<long long> a)
  • x :需要装的饼干袋的数量。
  • a :长度为 k 的数组。对 0 \le i \le k - 1 a_i 表示在食物储藏室里类型为 i 的饼干数量。
  • 此函数应当返回不同 y 值的数目,使得阿姨可以装出 x 袋饼干,且每袋饼干的总口味值都为 y
  • 此函数会被调用 q 次(对于允许的 q 值,详见约束条件和子任务部分)。每次调用应当被看成是独立的场景。

评测程序示例

评测程序示例将读取如下格式的输入数据。第一行包含一个整数 q 。接下来是 q 对这样的两行:它们按照下面的格式来描述一个单独的场景:

  • 第一行: k\ x
  • 第二行: a_0\ a_1\ \ldots\ a_{k - 1}

评测程序示例的输出结果的格式如下:

  • i 行( 1 \le i \le q ):count_tastiness 对于输入数据中第 i 个场景的返回值。

样例

样例输入 1

3 3
5 2 1

样例输出 1

5

样例说明 1

考虑以下调用:

count_tastiness(3, [5, 2, 1])

这意味着阿姨打算装 3 袋饼干,而在食物储藏室里总共有 3 种类型的饼干:

  • 5 块类型为 0 的饼干,每块的口味值为 1
  • 2 块类型为 1 的饼干,每块的口味值为 2
  • 1 块类型为 2 的饼干,其口味值为 4

y 能够取的值为 [0,1,2,3,4] 。举例来说,为了装出总口味值均为 3 3 袋饼干,阿姨可以这样装:

  • 一袋饼干里有 3 块类型为 0 的饼干,以及
  • 两袋饼干,其中各有一块类型为 0 的饼干和一块类型为 1 的饼干。

由于总共有 5 个可能的 y 值,函数应当返回 5

biscuits.png

样例输入 2

3 2
2 1 2

样例输出 2

6

样例说明 2

考虑如下调用:

count_tastiness(2, [2, 1, 2])

这意味着阿姨打算装 2 袋饼干,而在食物储藏室里总共有 3 种类型的饼干:

  • 2 块类型为 0 的饼干,每块的口味值为 1
  • 1 块类型为 1 的饼干,其口味值为 2
  • 2 块类型为 2 的饼干,每块的口味值为 4

y 能够取的值为 [0,1,2,4,5,6] ,由于总共有 6 个可能的 y 值,函数应当返回 6

数据范围与提示

对于全部数据,满足:

  • 1\le k\le 60
  • 1\le q\le 1000
  • 1\le x\le 10^{18}
  • 0\le a_i\le 10^{18} (对于所有的 0\le i\le k-1
  • 对于 count_tastiness 的每次调用,食物储藏室里所有饼干的口味值总和都不会超过 10^{18}

详细子任务分值与附加限制如下表:

子任务 附加限制 分值
1 q\le 10 ,且对于 count_tastiness 的每次调用,食物储藏室里所有饼干的口味值总和都不会超过 100\ 000 9
2 x=1,q\le 10 12
3 x\le 10\ 000,q\le 10 21
4 对于 count_tastiness 的每次调用,正确的返回结果都不会超过 200\ 000 35
5 没有附加限制条件。 23