Codeforces Round 975 (Div. 1) |
---|
Finished |
This is the hard version of the problem. In the three versions, the constraints on $$$n$$$ and the time limit are different. You can make hacks only if all the versions of the problem are solved.
This is the statement of Problem D1B:
You win if, for each $$$i$$$, you conquer city $$$i$$$ at a time no later than $$$a_i$$$. A winning strategy may or may not exist, also depending on the starting city. How many starting cities allow you to win?
For each $$$0 \leq k \leq n$$$, count the number of arrays of positive integers $$$a_1, a_2, \ldots, a_n$$$ such that
The answer can be very large, so you have to calculate it modulo a given prime $$$p$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3000$$$). The description of the test cases follows.
The only line of each test case contains two integers $$$n$$$, $$$p$$$ ($$$1 \le n \le 3000$$$, $$$10^8 \leq p \leq 10^9$$$, $$$p$$$ is prime) — the number of cities and the modulo.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$.
For each test case, output $$$n+1$$$ integers: the $$$i$$$-th integer should be the number of arrays that satisfy the conditions for $$$k = i-1$$$.
111 9982443532 9982443533 9982443534 9982443535 9982443536 9982443537 9982443538 9982443539 99824435310 10227585710 999662017
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
In the first test case,
In the second test case,
In the third test case,
Name |
---|