Trie

题意：给定 $n$ 个 01? 串，串中仅含 0、1、?，将 ? 替换成 0、1 中的一个。计算此时的 Trie 树的点数之和。题目已经令 $K$ 表示 ? 个数了。

观察到 $n$ 小，有人云：

状压DP、暴力搜索、指数容斥。

显然，我们考虑 DP，旁边的容斥。

不难发现，当确定了字符串时，Trie 树的节点个数是本质不同前缀个数 + 1。

于是，我们枚举前缀，计算他在这 $n$ 个字符串中出现的情况数。这是如果我们枚举了一个下标集合 $I$，有贡献 $(-1)^{|I|+1} \times f(I)$，$f(I)$ 表示这个前缀能否出现在我们枚举的下标集合对应的字符串，如果能，那么考虑全局的方案数

然而，这非常 LZ，考虑优化，由于每个前缀的权值都是 $1$，故可以枚举集合与前缀长度，判断这个集合有多少个可能均能够出现相同的前缀。注意这是迁全局的，要考虑不在下标集的字符串的贡献。

在已知字符串下标集合的条件下，我们枚举前缀。前缀的长度不超过集合中任何字符串的长度。

令 $out$ 表示集合外的 ? 个数，$cnt$ 是比枚举到的前缀小（不严格）的前缀，全是 ? 的个数。

设前缀长度为 $j$，原串是 $c$。

有以下情况：

• $\forall i \in I, c_{i, j} = ?$ ，此时有贡献 $2^{out + bck + cnt}$。加贡献之前 $cnt+1\to cnt$。其中 $bck$ 表示 $i$ 后面列的问号数。

• $\exist i \in I, c_{i, j} = 0$ 且 $\exist i \in I, c_{i, j} = 1$，不做贡献并马上退出。

• 否则，$2^{bck + out + cnt}$。

如果用 Gray-code 的枚举方法，复杂度正确 $\mathcal{O}(|S|2^n)$。

但是 $\mathcal{O}(|S|\times 2^n \times n)$，可以过本题。事实上，通过全部问号的数据可以 HACK 之。