#CW24. 覆盖(cover)
覆盖(cover)
题目描述
现在有一根长度为 的线段。这根线段上有 个标记。第 个标记位于线段左端向右第 的位置。
你要沿着这根线段,放置若干个木棒。放置木棒需要满足以下条件:
- 所有木棒长度必须为整数。
- 所有木棒不能互相重叠。
- 所有木棒需要将线段完全覆盖。也就是说,木棒不能超出线段的边界,即 ,也不能有线段的部分没有被木棒覆盖。
- 线段上有标记的地方,不能正好在两个木棒的边界处。
例如,对于一个长度为 的线段,如果在 处有标记,那么,你可以依次放置长度为 的木棒。因为它们完全覆盖了线段,并且在 处存在边界,这两个位置没有被标记。
对于一种木棒的摆放方案,它的价值定义为所有木棒长度的平方的乘积。
你需要求,满足上述条件的所有木棒摆放方案的价值之和是多少。你只需要输出这个价值和对 取模后的结果。
输入格式
第一行包含两个整数 。
接下来一行,包含 个整数表示 。
输出格式
输出一个整数,表示价值和对 取模后的结果。
样例 1 输入
3 1
2
样例 1 输出
13
样例 1 解释
可能的方案有以下两种:
- 左边放一个长为 的木棒,右边放一个长为 的木棒,价值为 ;
- 放一个长为 的木棒,价值为 。
样例 2 输入
10 9
1 2 3 4 5 6 7 8 9
样例 2 输出
100
数据范围
对于所有测试数据,保证:,,。
| 测试点 | ||
|---|---|---|