2617: 匹配数

admin

【题目描述】

一个匹配模式是由一些小写字母和问号'?'组成的一个字符串。当一个由小写字母组成的字符串s，长度和匹配模式长度相同，并且在对应的每一位都相等或模式串相应位置是‘？’，则称字符串s与这个模式相匹配。例如："abc"与"a?c"匹配地，但不与"a?b"或"abc?"相匹配。

现给你 M 个匹配模式，它们长度相同，问恰好与其中有 K 个模式相匹配的字符串有多少个？（答案模1,000,003）

【输入格式】

第一行，两个整数 M K。

下面有M行字符串，表示M个匹配模式。

【输出格式】

只一行，一个整数(模1000003之后)。

【输入输出样例】

输入	2 2 a? ?b	1   1   ?????
输出	1	881343

注：881343 =26^5 mod 1000003。

【数据范围】

1<= M <= 15

模式长度len:   1 <= len<= 50

1<= K <= M

模式中只含'a' - 'z'和 '?'

admin

方法一：用容斥原理做的。暴力在M个当中找出想要符合的K个模板串，计算出至少符合这K个模板串，那么其他的M-K个就不能符合，因此要减掉。如何减掉，要用容斥原理。减掉符合K+1个模版串的，加回符合K+2个模板串的……（也就是说，要减去在符合这K个模板串条件下，而且符合剩下的M-K个模板串当中的某个或某些的方案数。）
时间复杂度是O(C(M,K)*2^(M-K)*M*L)，超时。用记忆化，把至少符合不同状态下的模板串的方案数记下来。然后就可以省掉后面的M*L。
方法二：状态DP，F[i,S]记录到第i个字符，有哪些模式匹配（S二进制记录集合状态）时的方案数。最后统计一下即可。