题目描述
统计不含某些前缀的长为N的01串的个数
前缀数量为P。
容斥原理
满足前缀限定的01串个数为2^N - Sigma(2^(N-li)) +…,其中li为第i个前缀的长度
为了简化计算,先对前缀做一次筛选。如果有一个前缀包含另一个前缀,那么不用考虑它。
此时等式变为2^N - Sigma(2^(N-li))。
时间复杂度
O(N*p^2)
这里假设前缀比较长。
python3 代码
T = int(input())
for C in range(T):
n, p = map(int, input().split())
s = [0] * p
for i in range(p):
s[i] = input()
for i in range(p):
for j in range(p):
if (s[i].startswith(s[j]) and i!=j):
s[i] = 'None'
count = 2**n
for l in s:
if (l != 'None'):
count -= 2**(n-len(l))
print("Case #%d: %d"%(C+1, count))