Mojtaba and Construction camp II
Practice
5 (1 votes)
Algorithms
Fast fourier transform
Hard
Problem
82% Success 343 Attempts 50 Points 2s Time Limit 256MB Memory 1024 KB Max Code

Arpa and his friends are in a construction camp, their mission is to build and repair houses for poor people. Mojtaba is their commander. Totally there are $$n!$$ groups of students in camp, each group containing $$n$$ students. Camp lasts for $$\frac{n! \times (n! - 1)}{2}$$ days. Every they at 6 am Mojtaba rings the morning bell, all of the groups stand in their row. In each group, every person has an id from 1 to $$n$$, ids are unique. Also, groups are unique, i.e. there are no two groups with the same lineup. For example, if n = 3, here is the lineups:

  • Group #1: 1 2 3
  • Group #2: 1 3 2
  • Group #3: 2 1 3
  • Group #4: 2 3 1
  • Group #5: 3 1 2
  • Group #6: 3 2 1

After the national anthem, Mojtaba chooses 2 groups, persons with the same position and id in these two groups join each other and go for construction. Mojtaba never chooses the same pair of groups. Can you determine how many days at least $$k$$ pairs of students will go to construction till the end of camp?

In short, you need to find the number of ways to select $$2$$ distinct unordered permutations of size $$n$$ such that the permutations contain the same element on atleasy $$k$$ distinct indices . Print the answer modulo $$10^9+7$$. We don't know the number of students exactly, so print the answer for each $$n$$ from 1 to $$A$$.

Input Format

The first line contains two integers, A, k (\(1 \leq A, k \leq 2 \times 10^5\)).

Output Format

For each $$n$$ from 1 to $$A$$ print the answer.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
114 votes
Tags:
ApprovedEasyOpenPriority queueTrees
Points:50
6 votes
Tags:
Permutation and combinationDynamic Programming2D dynamic programmingFast Fourier transformAdvanced AlgorithmsAlgorithmsDivide-and-conquer algorithm
Points:50
4 votes
Tags:
AlgorithmsCombinatoricsFast Fourier transformHard