All Tracks Algorithms Problem

Connected Permutations
Tag(s):

Algorithms, Combinatorics, FFT, Hard, generating-functions

Problem
Editorial
Analytics

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
3
SAMPLE OUTPUT
1
1
3
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.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications