交流-题解（容斥原理+组合数）

原题

在此。

题目大意

给你$n$个字符串，其中选择$k$个，如果合法则将’?’变成字符（$26$个都可以，前提是合法）构成一个只含小写字母的字符串，求可以变成多少种字符串。 合法要求：一个位置上要不只有一种小写字母，要不是’?’。 解法：可以用状压$dp$或者容斥原理+组合数完成。

具体内容

首先铺垫三个内容：交集、并集、集合大小。

交集 用符号$\cap$表示，表示几个集合中都有的元素。并集 用符号$\cup$表示，表示几个集合中所有的元素（不算重复的）。集合大小 集合大小表示一个集合的元素个数。比如集合$A$的元素个数表示为$Card(A)$或$|A|$。

然后如果要求多个集合（分别为$a_1,a_2,\cdots ,a_n$）的并集，有公式 $\begin{array}{r}\left|a_1\cup a_2\cup \cdots \cup a_n\right|=\sum _{1\le i\le n}\left|a_i\right|-\sum _{1\le i<j\le n}\left|a_i\cap a_j\right|+\sum _{1\le i<j<k\le n}\left|a_i\cap a_j\cap a_k\right|-\dots +{\left(-1\right)}^{n+1}|a_1\cap a_2\cap \cdots \cap a_n|\end{array}$ 合并方案： 4. ‘?’与小写字母合并为小写字母 5. ‘?’与’?’合并成’?’ 6. 两个不同的小写字母合并无效，$return$

对于每一个$k\le i\le n$，然后合并我们可以求出$an{s}_i$表示$26$的（当$k=i$时合并这几个串）问号数量次幂之和。 然后我们就可以进行容斥。 可以发现，设答案为$answer$， 则 $\begin{array}{r}answer=\sum _{i=k}^{n}an{s}_i\times \left(-1or1\right)\times C_i^k\end{array}$ $-1$或$1$就是上面公式$+$或$-$，是奇负偶正。 具体为什么这么写，是因为我们构造了$n-k+1$个交集。然后每个并集分别为$C_i^{k}an{s}_i$。原来的再乘以与$k$可能重复的数量$C_i^k$。 具体实现时应该加上模数再模，以免负数情况。