#USACOC2222A. Drought
Drought
No testdata at current.
题目描述
Farmer John 的草地里的草在一场大旱中都干死了。经过数小时的绝望和沉思,FJ 想到了一个绝妙的主意,购买玉米来喂养他宝贵的奶牛。
FJ 的 头奶牛排成一行,队伍中的第 头奶牛的饥饿度为一个非负整数 。由于 FJ 的奶牛是社会性动物,她们坚持一起进食,FJ 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 和 并分别喂她们一袋玉米,令她们的饥饿度各减少 1。
FJ 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。尽管他不知道他的奶牛们具体的饥饿度,他知道每一头奶牛的饥饿度上界;具体地说,第 头奶牛的饥饿度 至多为 。
你的工作是计算符合上述上界的 元组 的数量,使得 FJ 有可能达到他的目标,答案对 取模。
输入格式
输入的第一行包含 。
第二行包含 。
输出格式
输出符合条件的饥饿度的 元组数量,对 取模。
3
9 11 7
3
9 11 7
共有 个 元组 与 相符合。
是其中一个元组。在这个情况中,有可能使得所有的奶牛具有相同的饥饿度:给奶牛 和 各两袋玉米,然后给奶牛 和 各五袋玉米,可以使得所有奶牛的饥饿度均为 。
是另一个元组。在这个情况中,不可能使得奶牛们的饥饿度相等。
4
6 8 5 9
4
6 8 5 9
测试点性质
编号为偶数的测试点中的 均为偶数,编号为奇数的测试点中的 均为奇数。
- 测试点 3-4 满足 以及 。
- 测试点 5-10 满足 以及 。
- 测试点 11-20 没有额外限制。
题目提供者
供题:Arpan Banerjee,Benjamin Qi