P2167 [SDOI2009]Bill的挑战

题目链接

题意:

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

  • (|t|=l)
  • (forall iin[1,l],t[i]=s_x[i] ext或s_x[i]= ?)

求有多少个串 (t) 恰好匹配 (k)(s_x)

(1leq nleq15,1leq lleq50,k≥1)

这数据范围爆搜就好了。

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

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

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

二项式反演基础

完整代码Link

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

个人博客地址: www.moyujiang.com 或 moyujiang.top
原文地址:https://www.cnblogs.com/moyujiang/p/14922076.html