Fern Market
题目描述
市场将开放 n 天,第 i 天每盆蕨类植物的价格为 ai。
你每天可以选择买入一盆、卖出一盆,或者不交易。一天内至多进行一次买入或卖出。没有植物时不能卖出;可以同时持有任意多盆植物,资金始终充足。
第 1 天开始时,你没有植物;第 n 天结束时,也必须没有植物。你事先知道所有天的价格,可以据此安排最优的交易方案。
定义 f(a1,a2,…,an) 为这种情况下可以获得的最大总利润。对每个正整数 n,再定义
g(n)=p∑f(p),
其中 p 遍历 (1,2,…,n) 的全部 n! 个排列。
给定正整数 k 和质数 m,求 g(1),g(2),…,g(k) 分别对 m 取模的结果。
输入格式
一行两个整数 k,m。
输出格式
输出 k 行,第 i 行为 g(i) 对 m 取模后的结果。
数据范围
- 1≤k≤7000。
- 108+7≤m≤109+7,保证 m 是质数。
- 每个输入文件只有一组数据。
样例输入 1
4 1000000007
样例输出 1
0
1
8
64
样例解释
当 n=1 时不能完成任何有收益的交易,所以 g(1)=0。
当 n=2 时,排列 (1,2) 可以先以 1 买入、再以 2 卖出,利润为 1;排列 (2,1) 的最大利润为 0,因此 g(2)=1。
当 n=3 时,六个排列的最大利润如下:
| 价格排列 |
最大利润 |
| (1,2,3) |
2 |
| (1,3,2) |
| (2,1,3) |
| (2,3,1) |
1 |
| (3,1,2) |
| (3,2,1) |
0 |
它们的利润之和为 8。
注意可以同时持有多盆植物。例如价格为 (2,1,4,3) 时,可以前两天各买入一盆,后两天各卖出一盆,利润为 4+3−2−1=4。