Connected Permutations

★★★★★

4.5

2 votes

Algorithms, Approved, Combinatorics, Fast Fourier transform, Hard, generating-functions

Details

Problem

We say that permutation p of size n is connected if there is no k, $1\leqslant k < n$ , such that $p(1), p(2), \dots, p(k)$ is permutation of $1,2,\dots, k.$
You are given a positive integer n. Find out number of connected permutations of size $1,2,\dots,n$ . As this numbers can be large, print them modulo $924844033.$

Input Format:
Single line containing integer n.

Output Format:
Output n lines, numbers of connected permutations of size $1, 2, \dots, n$ .

Constraints:
$1 \leqslant n \leqslant 500,000.$

50 points
$n \leqslant 5,000.$

Sample Input

Sample Output

1
1
3

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

(1) is connected permutation.
(2, 1) is connected permutation, (1, 2) is not.
(2, 3, 1), (3, 1, 2), (3, 2, 1) are connected permutations, (1, 2, 3), (1, 3, 2), (2, 1, 3) are not.

Contributers:

Artsem Zhuk

Lewin Gan