问题描述
Jack \texttt{Jack}Jack和Jill \texttt{Jill}Jill对抛硬币生成的序列模式感兴趣。给定抛硬币次数N NN和K KK个禁止的子模式，我们需要计算不包含任何禁止子模式的序列的概率。
输入：
- 每个测试用例包含两个整数N NN和K KK（1 ≤ N ≤ 50 1 \leq N \leq 501≤N≤50，0 ≤ K ≤ 50 0 \leq K \leq 500≤K≤50）
- 接下来K KK行，每行是一个由字符
H和T组成的子模式 - 所有子模式长度相同，且长度不超过10 1010
- 输入以N = K = 0 N = K = 0N=K=0结束
输出：
- 对于每个测试用例，输出概率的最简分数形式a / b a/ba/b，如果概率为0 00则输出
0
解题思路
1. 问题转化
这是一个典型的字符串模式匹配问题。我们需要统计长度为N NN的H/T序列中，不包含任何给定子模式的序列数量。
总序列数为2 N 2^N2N，因此：
概率 = 安全序列数 2 N \text{概率} = \frac{\text{安全序列数}}{2^N}概率=2N安全序列数
2. 关键观察
- 子模式长度固定：所有禁止子模式长度相同，设为M MM（M ≤ 10 M \leq 10M≤10）
- 状态表示：对于模式匹配问题，我们只需要关心序列的最后M MM个字符，因为更早的字符不会影响是否匹配长度为M MM的子模式
- 位掩码表示：可以用二进制位表示序列：
H→ 1T→ 0- 长度为M MM的子模式可以表示为一个M MM位二进制数
3. 算法设计
状态定义
设d p [ length ] [ mask ] dp[\texttt{length}][\texttt{mask}]dp[length][mask]表示：
- 当前序列长度为length \texttt{length}length
- 序列的最后M MM个字符（不足M MM位时用前导零补齐）的位掩码为mask \texttt{mask}mask
- 值为满足以上条件且不包含任何禁止子模式的序列数量
状态转移
从当前状态( length , mask ) (\texttt{length}, \texttt{mask})(length,mask)可以：
- 添加一个
H（二进制 1） - 添加一个
T（二进制 0）
新的掩码计算方式：
newMask = ( ( mask ≪ 1 ) & ( ( 1 ≪ M ) − 1 ) ) ∣ bit \texttt{newMask} = ((\texttt{mask} \ll 1) \& ((1 \ll M) - 1)) \mid \texttt{bit}newMask=((mask≪1)&((1≪M)−1))∣bit
其中：
<< 1表示左移一位，相当于去掉最旧的字符& ((1 << M) - 1)确保掩码保持在M MM位| bit添加新字符（0 00或1 11）
禁止模式检查
只有当序列长度≥ M − 1 \geq M-1≥M−1时，才需要检查新的掩码是否在禁止集合中：
- 如果newMask \texttt{newMask}newMask在禁止集合中，则跳过该转移
- 否则，继续递归
边界条件
- 当length = N \texttt{length} = Nlength=N时，找到一个安全序列，返回1 11
- 使用记忆化搜索避免重复计算
4. 特殊情况处理
- K = 0 K = 0K=0：没有禁止模式，所有2 N 2^N2N个序列都安全，概率为1 11
- M > N M > NM>N：禁止模式长度大于序列长度，不可能出现该模式，所有序列都安全，概率为1 11
- 否则：使用动态规划计算安全序列数
5. 概率计算
设安全序列数为safe \texttt{safe}safe，总序列数为2 N 2^N2N，则：
概率 = safe 2 N \text{概率} = \frac{\texttt{safe}}{2^N}概率=2Nsafe
需要化简为最简分数，使用gcd \gcdgcd函数求最大公约数。
算法复杂度分析
- 状态数：O ( N × 2 M ) O(N \times 2^M)O(N×2M)，其中M ≤ 10 M \leq 10M≤10
- 每个状态转移：O ( 1 ) O(1)O(1)
- 总复杂度：O ( N × 2 M ) O(N \times 2^M)O(N×2M)，对于N ≤ 50 N \leq 50N≤50完全可行
- 空间复杂度：O ( N × 2 M ) O(N \times 2^M)O(N×2M)
代码实现
// Playing with Coins// UVa ID: 10835// Verdict: Accepted// Submission Date: 2025-12-22// UVa Run Time: 0.020s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;set<int>forbidden;// 存储禁止模式的位掩码intN,K,M;// N:总长度, K:禁止模式数, M:模式长度longlongdp[64][1024];// dp[i][j]: 长度i，最后M位的掩码为j// 记忆化搜索longlongdfs(intlength,intmask){if(length>=N)return1LL;// 找到一个安全序列if(~dp[length][mask])returndp[length][mask];// 记忆化longlong&r=dp[length][mask];r=0;// 尝试添加 H(1) 或 T(0)for(inti=0;i<=1;i++){intnextMask=(((mask<<1)&((1<<M)-1)))|i;// 只有长度足够时才检查禁止模式if(length<M-1||!forbidden.count(nextMask))r+=dfs(length+1,nextMask);}returnr;}intmain(){intcaseNo=1;while(cin>>N>>K,N){cout<<"Case "<<caseNo++<<": ";forbidden.clear();// 读入禁止模式并转换为位掩码for(inti=0;i<K;i++){string pattern;cin>>pattern;M=pattern.length();intmask=0;for(autop:pattern)mask=(mask<<1)|(p=='H'?1:0);forbidden.insert(mask);}// 特殊情况处理：没有禁止模式或模式长度大于序列长度if(K==0||M>N){cout<<"1/1\n";continue;}// 动态规划计算安全序列数memset(dp,-1,sizeofdp);longlongsafe=dfs(0,0);// 输出结果if(safe==0)cout<<"0\n";else{longlongtotal=1LL<<N;longlongg=__gcd(safe,total);cout<<safe/g<<'/'<<total/g<<'\n';}}return0;}样例解析
样例输入
3 1 HH 3 1 HT 3 2 T H 0 0样例输出
Case 1: 5/8 Case 2: 1/2 Case 3: 0解释
Case 1 \texttt{Case 1}Case 1：
- N = 3 N = 3N=3，禁止模式：
HH（二进制 11） - 包含
HH的序列：HHH,HHT,THH（3个） - 安全序列：8 − 3 = 5 8 - 3 = 58−3=5个
- 概率：5 / 8 5/85/8
Case 2 \texttt{Case 2}Case 2：
- 禁止模式：
HT（二进制 10） - 包含
HT的序列：HHT,HTH,HTT,THT（4个） - 安全序列：4 44个
- 概率：4 / 8 = 1 / 2 4/8 = 1/24/8=1/2
Case 3 \texttt{Case 3}Case 3：
- 禁止模式：
T（0）和H（1） - 所有序列都至少包含一个
T或H - 安全序列：0 00个
- 概率：0 00
总结
本题通过位掩码 + 动态规划（记忆化搜索）的方法，高效地解决了模式匹配计数问题。关键点在于：
- 用二进制位表示字符序列，简化操作
- 只需维护最后M MM个字符的状态
- 记忆化搜索避免重复计算
- 特殊情况的预处理
