首先考虑，对于一个串 s 而言，直接统计比较麻烦，麻烦在难以体现「不认识」这个限制上。所以考虑如何忽略这个限制。考虑忽略限制后，就变成了统计 ans(s) 表示至少含有集合 s 的排列数。
那么对于 ans(s) 存在一个性质：如果 s 和 s' 中，连通分量状态相同，那么两个集合的 ans 是等价的。此处连通分量指的是连续一段互相认识的人，状态相同指的是 s 和 s' 的这些段大小相同，排布可以不同。（比如 0100111\Longleftrightarrow0011101\Longleftrightarrow1000111） 。
值得注意的是，对于一个长度为 k 的 1 连续段，其包含 k+1 个互相认识的人，也就是该连通块大小为 k+1 。
考虑如何求 ans(s) 。注意到现在已经转化成了统计每一种对 n 的拆分方式，有多少种排列数。那么一个比较自然的想法就是求下式
其中 t_i 表示枚举的第 i 个点集，s_i 表示组成 s 这个 01 串的第 i 个连通块(链形态的点集) ，f_{i,j} 表示从 size(i)=j 的集合 i 里面选出一个大小为 j 的链的方案数。不难知道这些限制的意义：划分必须恰好划分掉 n 个点，且点集之间不存在交集(否则需要合并)。
上式的意义在于，对于 s 的一个划分，每个连通块都需要从某个点集中选出，而点集之间是互不相交的，所以 size 必须恰好是链长。于是可以从这个角度入手来求排列数。同时需要注意，由于我们是硬生生划定了 p 个集合，并不关心集合之间是否有连边，也就代表了其中有些单点(也就是 s 中的 0 位置)可能是与其他连通块是一体的，这也就符合了我们对 ans(s) 的定义：至少含有集合 s 的排列数。
注意到 f 是比较容易求得的。考虑 g_{i,j} 表示集合 i 以 j 结尾的链的方案数，那么就是 n^2 转移，保证每次都用最后一个点转移就可以使得形态是一条链。f 就是对 g 的一个累加。这一部分复杂度 O(n^22^n) 。
考虑求出 f 之后如何计算这个式子。一个比较直接的想法是暴力枚举子集的子集来转移，由于 \Pi 对 \Sigma 有分配律，可知转移是不难的。复杂度 P(n)3^n，其中 P(n) 是本质不同的划分数。可以过掉 n=14 的 \rm F1 。