华师一附中OI组

标题: 2617: 匹配数 [打印本页]

作者: admin    时间: 2021-10-15 21:37
标题: 2617: 匹配数
【题目描述】
一个匹配模式是由一些小写字母和问号'?'组成的一个字符串。当一个由小写字母组成的字符串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    时间: 2021-10-15 21:37
方法一:用容斥原理做的。暴力在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二进制记录集合状态)时的方案数。最后统计一下即可。





欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2