← 完整题目索引

PROJECT EULER · #0553

幂集的幂集

Power Sets of Power Sets

仅题目 · 待解原题 ↗

设 P(n) 为第一个 n 正整数 {1,2,…,n} 的集合。
设 Q(n) 为 P(n) 所有非空子集的集合。
设R(n)为Q(n)的所有非空子集的集合。

元素 X∈R(n) 是 Q(n) 的非空子集,因此它本身就是一个集合。
从X我们可以构造一个图如下:

  • 每个元素Y∈X对应一个顶点,并标记为Y;
  • 如果 Y1∩Y2≠∅,则两个顶点 Y1 和 Y2 连接。

例如,X={{1},{1,2,3},{3},{5,6},{6,7}} 结果如下图:

0553-power-sets.gif

该图有两个连接的组件。

令 C(n,k) 为 R(n) 的元质数量,这些元素在其图中具有完全 k 的连通分量。
您获得 C(2,1)=6、C(3,1)=111、C(4,2)=486、C(100,10)mod1000000007=728209718。

查找 C(104,10)mod1000000007。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。