这是问题的简单版本。三个版本中,$$$n$$$ 的约束和时间限制是不同的。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
这是问题D1B的陈述:
- 连续有 $$$n$$$ 个城市,从左到右编号为 $$$1、2、\ldots、n$$$。 在$$$1$$$时刻,你只征服了一座城市,称为起始城市。 在时间$$$2, 3, \ldots, n$$$,你可以选择一个与迄今为止被征服的城市相邻的城市并征服它。如果对于每个 $$$i$$$,您在不晚于 $$$a_i$$$ 的时间征服城市 $$$i$$$,您就获胜。获胜策略可能存在也可能不存在,这也取决于起始城市。有多少个起始城市能让你获胜?
对于每个 $$$0 \leq k \leq n$$$,计算正整数数组 $$$a_1, a_2, \ldots, a_n$$$ 的数量,使得
- $$$1 \leq a_i \leq n$$$ 对于每个 $$$1 \leq i \leq n$$$;
- 问题 D1B 的答案是 $$$k$$$。
答案可能非常大,因此您必须以给定素数 $$$p$$$ 为模来计算它。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 80$$$)。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$n$$$, $$$p$$$ ($$$1 \le n \le 80$$$, $$$10^8 \leq p \leq 10^9$$$, $$$p$$$ 是素数) — 城市数量和模数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$80$$$。
输出
对于每个测试用例,输出 $$$n+1$$$ 个整数:第 $$$i$$$ 个整数应该是满足 $$$k = i-1$$$ 条件的数组的数量。
示例
输入 #1
11 1 998244353 2 998244353 3 998244353 4 998244353 5 998244353 6 998244353 7 998244353 8 998244353 9 998244353 10 102275857 10 999662017
输出 #1
0 1 1 2 1 14 7 4 2 183 34 19 16 4 2624 209 112 120 48 12 42605 1546 793 992 468 216 36 785910 13327 6556 9190 4672 2880 864 144 16382863 130922 61939 94992 50100 36960 14256 4608 576 382823936 1441729 657784 1086596 583344 488700 216000 96480 23040 2880 20300780 17572114 7751377 13641280 7376068 6810552 3269700 1785600 576000 144000 14400 944100756 17572114 7751377 13641280 7376068 6810552 3269700 1785600 576000 144000 14400
注意
在第一个测试用例中,
- 具有 $$$1$$$ 好的起始城市的数组:$$$[1]$$$。
在第二个测试用例中,
- 具有 $$$0$$$ 良好起始城市的数组:$$$[1, 1]$$$;
- 具有 $$$1$$$ 良好起始城市的数组:$$$[1, 2]$$$, $$$[2, 1]$$$;
- 具有 $$$2$$$ 良好起始城市的数组:$$$[2, 2]$$$。
在第三个测试用例中,
- 具有 $$$0$$$ 良好起始城市的数组:$$$[1, 1, 1]$$$, $$$[1, 1, 2]$$$, $$$[1, 1, 3]$$$, $$$[1, 2, 1]$$$, $$$[1, 2, 2]$$$, $$$[1, 3, 1]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 1]$$$, $$$[2, 1, 2]$$$, $$$[2, 2, 1]$$$, $$$[2, 2, 2]$$$, $$$[2, 3, 1]$$$, $$$[2, 3, 2]$$$, $$$[3, 1, 1]$$$;
- 具有 $$$1$$$ 良好起始城市的数组:$$$[1, 2, 3]$$$, $$$[1, 3, 3]$$$, $$$[2, 1, 3]$$$, $$$[3, 1, 2]$$$, $$$[3, 1, 3]$$$, $$$[3, 2, 1]$$$, $$$[3, 3, 1]$$$;
- 具有 $$$2$$$ 良好起始城市的数组:$$$[2, 2, 3]$$$, $$$[2, 3, 3]$$$, $$$[3, 2, 2]$$$, $$$[3, 3, 2]$$$;
- 具有 $$$3$$$ 良好起始城市的数组:$$$[3, 2, 3]$$$,$$$[3, 3, 3]$$$。