305782: CF1089I. Interval-Free Permutations
Memory Limit:512 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Interval-Free Permutations
题意翻译
给您一个模数 $p$ 和 $n$,请您输出长度为 $n$ 同时不包含连续子段的排列方案总数。 translated by @kyron✅题目描述
Consider a permutation $ p_1, p_2, \dots p_n $ of integers from 1 to $ n $ . We call a sub-segment $ p_l, p_{l+1}, \dots, p_{r-1}, p_{r} $ of the permutation an interval if it is a reordering of some set of consecutive integers. For example, the permutation $ (6,7,1,8,5,3,2,4) $ has the intervals $ (6,7) $ , $ (5,3,2,4) $ , $ (3,2) $ , and others. Each permutation has some trivial intervals — the full permutation itself and every single element. We call a permutation interval-free if it does not have non-trivial intervals. In other words, interval-free permutation does not have intervals of length between 2 and $ n - 1 $ inclusive. Your task is to count the number of interval-free permutations of length $ n $ modulo prime number $ p $ .输入输出格式
输入格式
In the first line of the input there are two integers $ t $ ( $ 1 \le t \le 400 $ ) and $ p $ ( $ 10^8 \le p \le 10^9 $ ) — the number of test cases to solve and the prime modulo. In each of the next $ t $ lines there is one integer $ n $ ( $ 1 \le n \le 400 $ ) — the length of the permutation.
输出格式
For each of $ t $ test cases print a single integer — the number of interval-free permutations modulo $ p $ .
输入输出样例
输入样例 #1
4 998244353
1
4
5
9
输出样例 #1
1
2
6
28146
输入样例 #2
1 437122297
20
输出样例 #2
67777575