#P10158. 钩子

    ID: 9273 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2300模拟概率DP数学动态规划概率论记忆化搜索区间DP

钩子

有 nn 个人要把外套挂到行李寄存处的 n+2n+2 个衣服钩子上。这些钩子从左往右等距排成一排,最左和最右两个钩子上挂着管事的人的衣服,这是不能动的。这些人要挂在剩下 nn 个钩子上。我们把这中间 nn 个钩子按左往右的顺序从 11 到 nn 编号。

现在 nn 个人依次把衣服挂上去,我们将这些人按先后顺序从 11 到 nn 编号。每个人都不喜欢和别人贴在一起,所以当一个人挂衣服时,他会计算每个空钩子 xx 和已经挂了衣服钩子的最短距离 dxd_x,以及 d=max⁡{dx}d = \max\{d_x\},之后他会在所有满足 dx=dd_x=d 的衣服钩子 xx 中等概率随机挑选一个挂上衣服。

给定 nn 和质数 PP,我们希望你对于 1≤i,j≤n1 \le i,j \le n 都计算出,ii 号人把衣服挂在 jj 号钩子上的概率,对 PP 取模的结果。

数据保证答案概率可以表示成既约分数 x/yx/y,且 yy 不是 PP 的倍数,那么你只需输出 x×yP−2 mod Px \times y^{P-2} \bmod P.

输入格式

仅一行两个整数 nn 和 PP.

输出格式

输出 nn 行,每行 nn 个数,第 ii 行的第 jj 个数表示 ii 号人把衣服挂在 jj 号钩子上的概率,对 PP 取模的结果。

输入输出中相邻两个整数用空格隔开。

样例 1 输入

3 1000000007

样例 1 输出

0 1 0
500000004 0 500000004
500000004 0 500000004

样例 2 输入

4 1000000007

样例 2 输出

0 500000004 500000004 0
333333336 166666668 166666668 333333336
333333336 166666668 166666668 333333336
333333336 166666668 166666668 333333336

子任务

对于所有数据,保证 1≤n≤1000,109<P<1.1×1091 \le n \le 1000,10^9<P<1.1 \times 10^9 且 PP 是质数。

  1. n≤20n \le 20(10 分)
  2. n≤30n \le 30(10 分)
  3. n≤50n \le 50(25 分)
  4. n≤100n \le 100(20 分)
  5. n≤300n \le 300(15 分)
  6. 没有特殊限制(20 分)

时间限制:1s\texttt{1s}

空间限制:512MB\texttt{512MB}