UVa 10835 Playing with Coins

问题描述

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. 关键观察

1. 子模式长度固定：所有禁止子模式长度相同，设为M MM（M ≤ 10 M \leq 10M≤10）
2. 状态表示：对于模式匹配问题，我们只需要关心序列的最后M MM个字符，因为更早的字符不会影响是否匹配长度为M MM的子模式
3. 位掩码表示：可以用二进制位表示序列：
   • H→ 1
   • T→ 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)可以：

1. 添加一个H（二进制 1）
2. 添加一个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. 特殊情况处理

1. K = 0 K = 0K=0：没有禁止模式，所有2 N 2^N2N个序列都安全，概率为1 11
2. M > N M > NM>N：禁止模式长度大于序列长度，不可能出现该模式，所有序列都安全，概率为1 11
3. 否则：使用动态规划计算安全序列数

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

总结

本题通过位掩码 + 动态规划（记忆化搜索）的方法，高效地解决了模式匹配计数问题。关键点在于：

1. 用二进制位表示字符序列，简化操作
2. 只需维护最后M MM个字符的状态
3. 记忆化搜索避免重复计算
4. 特殊情况的预处理