P8417 [THUPC 2022 Final] Introduction to High-Performance Computing: Cluster Login Password Complexity Policy

Introduction to High-Performance Computing is a specialized elective course offered by the Department of Computer Science at T University. This course covers the basic concepts and principles of high-performance computing, common parallel programming models and basic ideas for writing parallel programs, basic methods for program performance analysis and optimization, and the relationship between computer architecture and program performance. To let students experience parallel programming, performance analysis, and optimization in practice, the course provides a cluster consisting of five servers. Each server is equipped with a $2$ socket $\times\ 14$ core processor and $1$ GPU. Students enrolled in the course can do message-passing parallel programming, shared-memory parallel programming, and CUDA programming on the cluster. To prevent valuable computing resources from being abused (for example, secretly using the servers for crypto mining), the course has many rules for using the cluster, including requiring students to use strong cluster login passwords.

To ensure that students use sufficiently strong cluster login passwords, the course staff configured a password complexity policy on the cluster. At the beginning of the semester, every student receives a randomly generated initial password. After logging into the cluster with the initial password, the cluster requires the student to enter a new password. Only after changing the password can the student access the cluster normally. In this problem, we assume the password complexity policy is: - The password contains at least $L$ characters, and contains at least one digit and at least one letter. - The password must not contain **$A$ consecutive** **identical** characters. For example, `2333` contains $3$ consecutive identical characters. - The password must not contain an increasing sequence or decreasing sequence made of **$B$ consecutive** characters. Here, an increasing sequence is defined as a **contiguous substring** of one of the three strings `0123456789`, `ABCDEFGHIJKLMNOPQRSTUVWXYZ`, and `abcdefghijklmnopqrstuvwxyz`. A decreasing sequence is the reverse of a contiguous substring of one of these three strings. For example: - `6789` is an increasing sequence of length $4$, and `FED` is a decreasing sequence of length $3$. - `90`, `AZ`, and `az` are not increasing or decreasing sequences. - `GPU` is not an increasing sequence because it is not contiguous. - `Def` is not an increasing sequence because the letter cases are inconsistent (but it contains an increasing contiguous subsequence `ef` of length $2$). - `1112345678999` is not an increasing sequence, but its subsequence `123456789` is increasing. Assume the password consists only of digits and uppercase/lowercase letters. Among all passwords with length not exceeding $R$, compute how many passwords satisfy the password complexity policy.

The input contains one line with four positive integers $L, R, A, B$, whose meanings are as described above.

Output a non-negative integer, representing the number of passwords that satisfy the password complexity policy and have length not exceeding $R$, modulo $1,000,000,007$.

[Sample 1 Explanation] Because the password must contain at least one digit and at least one letter, there are $2\times 10 \times (26\times 2) = 1040$ valid passwords. [Constraints] It is guaranteed that $1\le L\le R\le 10^9$, $2\le A\le 6$, $2\le B\le 26$. [Hint] If you do not want to remember a long and complex password, and do not want to type it manually every time you log in, you can also set up a public key for SSH login. Translated by ChatGPT 5