题目链接

题意:

给定 $n$ 个长度为 $l$ 的字符串 $s_{1...n}$,串由小写字母和字符 ? 构成,定义串 $s_x$ 和串 $t$ 匹配,当且仅当满足:

  • $|t|=l$
  • $\forall i\in[1,l],t[i]=s_x[i]\text或s_x[i]= ?$

求有多少个串 $t$ 恰好匹配 $k$ 个 $s_x$。

$1\leq n\leq15,1\leq l\leq50,k≥1$。

这数据范围爆搜就好了。

枚举选 $k$ 个串匹配,每个位置要么有固定的字母,要不就全是 ?,统计一下即可。这一步是爆搜,时间复杂度 $O(2^n*n*l)$

但是发现它可能不一定只匹配了枚举的这 $k$ 个串,比如 $5$ 个串的所有元素都是 ?, $k=1$,答案就是 $0$。

于是我们发现,刚刚枚举的是至少匹配我们选择的 $k$ 个串的串数,而题目要求的是恰好匹配 $k$ 个串的串数,所以套个二项式反演就好了。

二项式反演基础

完整代码Link

还是蛮快的,我这样的大常数选手都能不开 O2 卡进最优解第一页。

最后修改:2021 年 04 月 19 日 10 : 37 PM