高二高一初三模拟赛25 总结

前言

这次比赛比较简单，然而T1太自信结果炸了，T3脑子坏掉又写错了，真是没办法啊，分数就白白丢掉了好多。。

匹配数

题目描述

一个匹配模式是由一些小写字母和问号’?’组成的一个字符串。当一个由小写字母组成的字符串s，长度和匹配模式长度相同，并且在对应的每一位都相等或模式串相应位置是‘？’，则称字符串s与这个模式相匹配。例如：”abc”与”a?c”匹配地，但不与”a?b”或”abc?”相匹配。
现给你 M 个匹配模式，它们长度相同，问恰好与其中有 K 个模式相匹配的字符串有多少个？（答案模1,000,003）

输入格式

第一行，两个整数 M K。
下面有M行字符串，表示M个匹配模式。

1<= M <= 15
模式长度len满足：1 <= len<= 50
1 <= K <=M
模式中只含小写英文字母和 ‘?’

输出格式

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

输入样例

样例1：

2 2
a?
?b

样例2

1 1
?????

输出样例

样例1：

1

样例2：

881343
（注：881343 = 26^5 mod 1000003。）

题解(容斥原理)

这题可以用很暴力的状压dp切掉，但是优美的方法是容斥原理。

就是那个被大佬们成为广义容斥原理的东东。

首先注意题目求的是恰好k个匹配。我们枚举出所有状态，然后看看有几个匹配，假如有k个匹配就加进答案。但是可能匹配有多，假如匹配了k+1个就要减，但是减多了k+2的加回来。于是就是一个容斥原理了。

但是广义在于哪里呢？一开始我错了，原因在于假如匹配了k+1的方案数，对k答案的贡献是要被减去的，但减去可不止一个！设方案为v，次数就是$C_{k+1}^k$，于是当前匹配了p个模式，贡献就是 Ckp

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！