TrickyInequality | Topcoder Archive

Problem Statement

This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.

There are m positive integer variables: x₁, x₂, ..., x_m. We do not know their exact values, we only know some inequalities they satisfy:

The sum of all our variables is at most s. Formally: x₁ + x₂ + ... + x_m <= s.
Each of the first n variables is less than or equal to t. Formally: for each i such that 1 <= i <= n we have x_i <= t.

You are given the long s and the ints t, n, and m. Compute and return the number of solutions to the above inequalities, modulo 1,000,000,007.

Definition

Class:: TrickyInequality
Method:: countSolutions
Parameters:: long, int, int, int
Returns:: int
Method signature:: int countSolutions(long s, int t, int n, int m)
(be sure your method is public)

Constraints

m will be between 1 and 10^9, inclusive.
n will be between max(1,m-100) and m, inclusive.
t will be between 1 and 10^5, inclusive.
s will be between n*t and 10^18, inclusive.

Examples

```
3
```
```
1
```
```
1
```
```
2
```
```
Returns: 2
```
In this test case we have two variables, and we know that their sum is at most 3 and that the first variable is at most 1. Formally, we have x1 + x2 <= 3 and x1 <= 1. There are only two solutions in positive integers: (1,1) and (1,2).
```
5
```
```
2
```
```
2
```
```
3
```
```
Returns: 8
```
Here we are given the following inequalities: x1 + x2 + x3 <= 5 x1 <= 2 x2 <= 2 There are 8 solutions: (1,1,1), (1,1,2), (1,1,3), (1,2,1), (1,2,2), (2,1,1), (2,1,2) and (2,2,1).
```
30
```
```
1
```
```
1
```
```
10
```
```
Returns: 10015005
```
From the constraints we know that x1 must be 1. Therefore the sum of the nine positive integers x2 through x10 has to be at most 29. It's not hard to find that the answer is the binomial coefficient C(29,9) = 10015005.
```
2000
```
```
20
```
```
100
```
```
200
```
```
Returns: 35422605
```

999999999999999999

999999900

1000000000

Returns: 90919453

999999999999999999

1000000000

1000000000

Returns: 297793005

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.