垫脚石（相关题 → 此题） 2015 年湖北预赛 第 2 题 · P010113
两题的覆盖要求都可编码为“每个目标类别至少出现一次”，再对缺少类别的事件作分类或容斥。
分配到村庄时各人独立选择；密码题还须保留相邻不同的限制，删掉类别后的词数不能直接用独立选择的幂。
培玉 · 一试
2025 年重庆预赛
三类字符五位密码计数
F2填空题排列组合
可以使用字符 组成五位密码，要求必须包含数字、小写字母和大写字母，且不可以出现两个相同的字符相邻。例如密码可以设置为 或 ，但不能设置为 或 。则可以设置的不同密码个数为。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
先只处理相邻不同，再按实际使用的字符类型数排除只含一种或两种类型的密码。
想想一道相关的题
先回想这道题的想法，再试试当前题。
解答
只要求相邻字符不同时，共有
个密码。只含一种字符类型的密码有
个。固定两种字符类型时，使用这 个字符且相邻不同的序列有 个；其中只使用某一种类型的共有 个。因此恰含这两种类型的有 个。三对字符类型给出
个。故满足三种类型都出现的密码数为
复核
“只含一种”和“恰含两种”互不相交；恰含两种的密码由其类型对唯一确定，没有重复计数。
方法总结
同时含若干类别并带相邻限制的排列计数，可先在给定字符集上数相邻不同序列，再按实际出现的类别数作容斥或分类扣除。
为什么评为 F2（会透露解法方向）
先数相邻不同的序列，再按实际出现的一类或两类字符扣除，分类仅取决于字符类型。
联系 · 1 条
已记下，谢谢！