{"problem":{"name":"[THUPC 2022 决赛] 高性能计算导论集群登录密码复杂性策略","description":{"content":"为了确保选课同学使用了较强的集群登录密码，课程组在集群上配置了密码复杂性策略。所有选课的同学在学期初会收到随机生成的初始密码。在使用初始密码登录集群后，集群会要求同学输入新的密码，密码更改完毕后才能正常访问集群。在本题中，我们假设密码复杂性策略为： - 密码至少包含 $L$ 个字符，且至少包含一个数字和一个字母； - 密码不能包含**连续** $A$ 个**重复**字符，如 `2333` 包含","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8417"},"statements":[{"statement_type":"Markdown","content":"为了确保选课同学使用了较强的集群登录密码，课程组在集群上配置了密码复杂性策略。所有选课的同学在学期初会收到随机生成的初始密码。在使用初始密码登录集群后，集群会要求同学输入新的密码，密码更改完毕后才能正常访问集群。在本题中，我们假设密码复杂性策略为：\n\n- 密码至少包含 $L$ 个字符，且至少包含一个数字和一个字母；\n\n- 密码不能包含**连续** $A$ 个**重复**字符，如 `2333` 包含了连续 3 个重复字符；\n\n- 密码不能包含**连续** $B$ 个字符组成的上升序列或下降序列，其中定义上升序列为 `0123456789`，`ABCDEFGHIJKLMNOPQRSTUVWXYZ` 和 `abcdefghijklmnopqrstuvwxyz` 三个字符串中某一个串的**连续**子串，下降序列为这三个字符串中某一个串的**连续**子串的反向串，例如： \n  \n  - `6789` 是长度为 4 的上升序列，`FED` 是长度为 3 的下降序列；\n  \n  - `90`、`AZ`、`az` 不是上升序列或下降序列；\n  \n  - `GPU` 不是上升序列，因为它不连续；\n  \n  - `Def` 不是上升序列，因为字母大小写不一致（但它包含长度为 2 的上升连续子序列 `ef`）；\n  \n  - `1112345678999` 不是上升序列，但它的子序列 `123456789` 是上升的。\n\n假设密码仅由数字及大小写字母构成。求在长度不超过 $R$ 的所有密码中，有多少个密码满足密码复杂性策略。\n\n## Input\n\n输入仅一行，包括四个正整数 $L, R, A, B$，含义如题目描述中所述。\n\n## Output\n\n输出一个非负整数，表示满足密码复杂性策略且长度不超过 $R$ 的密码数量对 $1,000,000,007$ 取模的结果。\n\n[samples]\n\n## Background\n\n高性能计算导论是 T 大学 C 系开设的一门专业选修课。这门课程讲述了高性能计算的基本概念和原理，常见并行编程模型及并行程序的基本编写思路，程序性能分析和优化的基本方法，以及计算机体系结构和程序性能的关系。为了让同学们能够实际体验并行程序的编写、性能分析和优化，课程为同学们提供了五台服务器组成的集群，每台服务器上都配置了 2 socket × 14 core 的处理器和 1 块 GPU。选课的同学可以在集群上进行基于消息传递的并行编程、基于共享内存模型的并行编程和 CUDA 编程。为了防止宝贵的计算资源被滥用（比如偷偷用服务器挖矿），课程在集群使用上有很多的规定，其中就包括要求选课同学使用高强度的集群登录密码。\n\n## Note\n\n【样例 1 解释】\n\n因为密码必须至少包含一个数字和一个字母，所以满足要求的密码有 $2\\times 10 \\times (26\\times 2) = 1040$ 种。\n\n【数据范围与约定】\n\n保证 $1\\le L\\le R\\le 10^9$，$2\\le A\\le 6$，$2\\le B\\le 26$。\n\n【提示】\n\n如果你不想记住又长又复杂的密码，不想每次登录时手动输入密码，也可以配置公钥进行 SSH 登录。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8417","tags":["2022","O2优化","THUPC"],"sample_group":[["2 2 2 2\n","1040\n"],["12 24 3 4\n","718185656\n"],["100 10000000 6 6\n","146399052\n"]],"created_at":"2026-03-03 11:09:25"}}