给你 n 个字符串,每个字符串长度为 m,每个字符串由小写英文字母和 ? 构成,其中 ? 表示这一位可以随便填。
求将所有字符串插入一颗 Trie 树的期望节点数量。
数据范围:1≤n≤12,1≤m≤1000
时间限制:2s。
求 Trie 树期望大小等价于求所有字符串对应的 Trie 树节点之并,形式化的讲:
E[∪i=1nSi]
显然这个并集不好看,直接应用容斥原理:
E[∪i=1nSi]=ET⊆{1,2,⋯,n}∑(−1)∣T∣+1⋅∣∩i∈TSi∣
利用线性性,将其化简一下:
E[∪i=1nSi]=T⊆{1,2,⋯,n}∑(−1)∣T∣+1⋅E[∣∩i∈TSi∣]
现在就可以直接枚举 {1,2,⋯,n} 的子集,然后枚举深度 i∈[1,m] 分别计算概率 pi,最终答案即为 1+∑i=1∏j=1ipj⋅1。
这样做的复杂度为 O(nm2n)。