#PQJ82x465. QOJ 82_465

    ID: 3042 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:GZOI 2017组合数学

QOJ 82_465

Alice 和 Bob 在玩一个古老的游戏。现在有若干堆石子,Alice 和 Bob 轮流取,每次可以选择其中某一堆的石子中取出任意颗石子,但不能不取,谁先取完使得另一个人不能取了算赢。

现在场地上有 𝑁 堆石子,编号为 1 至 𝑁 。Alice 很快发现了这个游戏存在一些固定的策略。阴险的 Alice 想赢得这场比赛就来找到主办方你,希望你在这 𝑁 堆石子中选出若干堆石子作为最后游戏用的石子堆并使得 Alice 能获得胜利。你自然不想让 Alice 得逞,所以你提出了一个条件:Alice 在这个游戏中第一次取的那堆石子的编号需要你来指定(仅指定取的石子堆编号,不指定第一次取多少个,这个指定的石子堆必然包含在最后游戏用的石子堆中)。

现在你很好奇,你想算算有多少种方案让 Alice 不能获胜。注意,即使选出的石子堆的编号的集合完全相同,指定第一次取的石子堆的编号不同,也认为方案是不同的。

输入格式

第一行,一个正整数 𝑁 ,表示石子堆数。

第二行, 𝑁 个正整数,表示各堆石子的数量,按编号 1 至 𝑁 依次给出。

输出格式

一行,表示方案数。答案对 10 9 + 7 取模。

样例数据 样例 1 输入 3 2 4 5 样例 1 输出 5 样例 1 解释

第一种:选编号 1 和编号 2 ,指定编号 1 。

第二种:选编号 1 和编号 3 ,指定编号 1 。

第三种:选编号 1 、编号 2 和编号 3 ,指定编号 2 。

第四种:选编号 1 、编号 2 和编号 3 ,指定编号 3 。

第五种:选编号 2 和编号 3 ,指定编号 2 。

样例 2 输入 3 1 2 2 样例 2 输出 6 子任务 数据编号 𝑁 每堆石子数量

1

≤ 5

≤ 5

2

≤ 10

≤ 10

3

≤ 100

≤ 100

4

≤ 200

≤ 200

5