Codeforces Round 975 (Div. 1) |
---|
Закончено |
Это средняя версия задачи. В трёх версиях ограничения на $$$n$$$ и ограничение по времени отличаются. Вы можете совершать взломы только в том случае, если решены все версии задачи.
Это условие задачи D1B:
Вы выиграете, если для каждого $$$i$$$ вы захватите город $$$i$$$ в момент времени не позже, чем $$$a_i$$$. Выигрышная стратегия может существовать, а может и не существовать, в том числе в зависимости от стартового города. Сколько стартовых городов позволяют вам выиграть?
Для каждого $$$0 \leq k \leq n$$$ подсчитайте количество массивов целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$ таких, что
Ответ может быть очень большим, поэтому вы должны вычислить его по модулю заданного простого числа $$$p$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$p$$$ ($$$1 \le n \le 500$$$, $$$10^8 \leq p \leq 10^9$$$, $$$p$$$ — простое) — количество городов и модуль.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$500$$$.
Для каждого набора входных данных выведите $$$n+1$$$ целых чисел: $$$i$$$-е целое число должно равняться количеству массивов, удовлетворяющих условиям для $$$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
В первом наборе входных данных,
Во втором наборе входных данных,
В третьем наборе входных данных,
Название |
---|