B. 2B | A trip to Macao

    传统题 2000ms 16MiB

2B | A trip to Macao

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

贡献名单

想法 标程 数据 验题 题解
xiaohaoaibiancheng66 喵仔牛奶 xiaohaoaibiancheng66

题目背景

本题有两个等价的题目描述,以分割线分割,阅读一个即可!

这天,xhabc66 来到澳门旅游。一下飞机,他直奔赌场。

可是,今天的赌场格外热闹,不知发生了什么。

xhabc66 打开手机一看:啊,原来今天是 12122020 日!

因此,赌场在做活动!一年一度!机不可失!

xhabc66 径直走进了赌场。

题目描述

求有多少个数列 {bk}\{b_k\} 满足:

  1. i[1,k],biN\forall i \in [1,k],b_i \in \mathbb{N^*}
  2. $\forall i \in [2,k],b_i \in [b_{i-1}+1,b_{i-1} \times 2]$;
  3. b1{am}b_1 \in\{a_m\}
  4. bk=nb_k=n

答案对 109+710^9+7 取模。

数列的长度 kk 可以是任何正整数(当然,不能是 00)。


赌场贴出了如下规则(你可以忽略没有加粗的内容):

  1. 所有玩家在注册后方可进行游戏。
  2. 活动期间,新注册的玩家可从抽奖盒内拿走一枚筹码。抽奖盒内共 mm 种筹码,面值分别为 a1,a2,,ama_1,a_2,\ldots,a_m 澳元(均为正整数),每种一个,保证公平。
  3. 本赌场仅提供一种游戏:猜拳。游戏开始时,双方各下注相同数量(以 11 澳元为单位)的筹码;若猜拳分出胜负,则胜者拿走所有下注。
  4. 根据上一条可知,玩家一次游戏中赢得的筹码(正整数)不得超过自身所携带的筹码
  5. 公平游戏,严禁作弊,违者严惩。

xhabc66 注册后,连赢数局(可以是 00 局,但没有输过,也没有平局过),最终带着 nn 澳元走出了赌场。

出赌场后,xhabc66 突然好奇他是怎么赢到这么多钱的。然而,他不记得他每局下了多少注,不记得他一共玩了多少局,甚至不记得他开始时拿走的筹码是什么面值。

他想知道:他有多少种不同的赢钱方法。

答案对 109+710^9+7 取模。

两种赢钱方法在满足以下任何一个条件时,xhabc66 都会认为它们不同:

  • 他某一局的下注金额不同;
  • 他玩的局数不同;
  • 他开始时拿走的筹码的面值不同。

输入格式

两行。

第一行,两个正整数,n,mn,m

第二行,mm从小到大排列的正整数,a1ama_1 \sim a_m

输出格式

一行一个正整数,表示答案。

样例 #1

样例输入 #1

4 4
1 2 3 4

样例输出 #1

6

样例 #2

样例输入 #2

5 1
1

样例输出 #2

3

样例 #3

样例输入 #3

12345678 9
1 2 3 45 67 89 123 456 789

样例输出 #3

998899106

提示

样例 11 解释:

1 2 3 4
1 2 4
2 3 4
2 4
3 4
4

样例 22 解释:

1 2 3 4 5
1 2 3 5
1 2 4 5

本题采用捆绑测试。

Subtask 编号 mm \le nn \le 分值
00 33 2020
11 10510^5 4040
22 10610^6 10810^8

对于 100%100\% 的数据,1m1061 \le m \le 10^61a1<a2<<amn1081 \le a_1<a_2<\ldots<a_m \le n \le 10^8mnm \le n

提示: 请注意本题不同寻常的内存限制!

FAOI-R2

未参加
状态
已结束
规则
IOI
题目
4
开始于
2024-1-1 17:00
结束于
2024-1-1 21:00
持续时间
4 小时
主持人
参赛人数
5