Passwords | Topcoder Archive

Problem Statement

A password is a sequence of alphanumeric characters. Count the number of different passwords of length N which contain at least L lowercase characters, at least U uppercase characters and at least D digits. Return this number modulo 1,000,000,009.

Definition

Class:: Passwords
Method:: countValid
Parameters:: int, int, int, int
Returns:: int
Method signature:: int countValid(int N, int L, int U, int D)
(be sure your method is public)

Constraints

N will be between 1 and 200,000, inclusive.
L will be between 0 and N, inclusive.
U will be between 0 and N, inclusive.
D will be between 0 and N, inclusive.

Examples

```
2
```
```
0
```
```
0
```
```
2
```
```
Returns: 100
```
The only valid passwords are those consisting of digits only. There are 100 2-digit sequences.
```
3
```
```
1
```
```
1
```
```
1
```
```
Returns: 40560
```
A valid password will contain exactly one lowercase and one uppercase letter and one digit. Since they can come in any order, there are 3!*26*26*10 = 40560 possible combinations.
```
4
```
```
1
```
```
1
```
```
1
```
```
Returns: 5029440
```
This time, the exact number of characters of each type is undefined.
```
10
```
```
1
```
```
3
```
```
3
```
```
Returns: 818019214
```
```
5
```
```
2
```
```
2
```
```
2
```
```
Returns: 0
```

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.