Need help with this problem

There are n people, numbered 1 through n .

We want to divide them into a number of groups, under the following two conditions:

  • Every group contains between a and b people, inclusive of both a and b.
  • Let Fi be the number of the groups containing exactly i people. Then, for all i , either Fi=0 or c <= Fi <= d holds.

Find the number of ways to divide the people into groups. Now two ways to divide them into groups is considered different if there exists two people such that they belong to the same group in exactly one of the 2 ways. Print the answer in 109+7 modulo.

Constraints:

  • 1 <= n <= 103
  • 1 <= a <= b <= n
  • 1 <= c <= d <= n

Input Format

The line containing 5 integers n, a, b, c, and d.

Output Format

Print the number of ways to divide the people into groups in 109+7 modulo.

Link to original problem? Somehow I doubt that the limit of n is one hundred and three, and that we have to output the result modulo 116 XD

1 Like

dp(i, j) as the number of ways we can distribute j people into valid groups with size <= i.
Call another f(i, j, k) as number of ways to distribute k people into j groups, all size i. Transitions can be done by prefix sum in O(N ^ 3).
Define cnt(i, k) as number of ways to distribute k people into groups, all size i. cnt(i, k) is sum of all f(i, j, k), O(N ^ 3) to calculate.
Finally, using cnt array we can do transitions in DP in O(N ^ 3).

can you please explain via pseudo code?? i can’t get your logic!

unable to crack ur logic… could u please explain via code

You must provide a link to the problem.

1 Like

Philips coding challenge?

What’s difficult about it? I don’t want to bother writing code for problems that I’m not solving myself, even psuedo. Just say the hard part and I’ll try explaining