#P18365. Fern Market

Fern Market

Fern Market

题目描述

市场将开放 nn 天,第 ii 天每盆蕨类植物的价格为 aia_i。

你每天可以选择买入一盆、卖出一盆,或者不交易。一天内至多进行一次买入或卖出。没有植物时不能卖出;可以同时持有任意多盆植物,资金始终充足。

第 1 天开始时,你没有植物;第 nn 天结束时,也必须没有植物。你事先知道所有天的价格,可以据此安排最优的交易方案。

定义 f(a1,a2,…,an)f(a_1,a_2,\ldots,a_n) 为这种情况下可以获得的最大总利润。对每个正整数 nn,再定义

g(n)=∑pf(p),g(n)=\sum_{p} f(p),

其中 pp 遍历 (1,2,…,n)(1,2,\ldots,n) 的全部 n!n! 个排列。

给定正整数 kk 和质数 mm,求 g(1),g(2),…,g(k)g(1),g(2),\ldots,g(k) 分别对 mm 取模的结果。

输入格式

一行两个整数 k,mk,m。

输出格式

输出 kk 行,第 ii 行为 g(i)g(i) 对 mm 取模后的结果。

数据范围

  • 1≤k≤70001\le k\le7000。
  • 108+7≤m≤109+710^8+7\le m\le10^9+7,保证 mm 是质数。
  • 每个输入文件只有一组数据。

样例输入 1

4 1000000007

样例输出 1

0
1
8
64

样例解释

当 n=1n=1 时不能完成任何有收益的交易,所以 g(1)=0g(1)=0。

当 n=2n=2 时,排列 (1,2)(1,2) 可以先以 1 买入、再以 2 卖出,利润为 1;排列 (2,1)(2,1) 的最大利润为 0,因此 g(2)=1g(2)=1。

当 n=3n=3 时,六个排列的最大利润如下:

价格排列 最大利润
(1,2,3)(1,2,3) 2
(1,3,2)(1,3,2)
(2,1,3)(2,1,3)
(2,3,1)(2,3,1) 1
(3,1,2)(3,1,2)
(3,2,1)(3,2,1) 0

它们的利润之和为 8。

注意可以同时持有多盆植物。例如价格为 (2,1,4,3)(2,1,4,3) 时,可以前两天各买入一盆,后两天各卖出一盆,利润为 4+3−2−1=44+3-2-1=4。