Problem 553 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Problem 553 へ行く。
• Problem 553 の差分を削除

#author("2024-01-12T02:17:08+00:00","","")
#author("2024-01-12T02:17:40+00:00","","")
*[[Problem 553:http://projecteuler.net/problem=553]] 「べき集合のべき集合」 [#sfa14e9b]

P(n) を n 以下の正整数の集合 {1,2,...,n} とする。&br;
Q(n) を P(n) の空でない部分集合全体からなる集合とする。&br;
R(n) を Q(n) の空でない部分集合全体からなる集合とする。

元 X ∈ R(n) は Q(n) の空でない部分集合なので、それ自体が集合である。&br;
X から次のようにしてグラフを作る。

- 各 Y ∈ X は、Y をラベルとする頂点に対応する
- 2つの頂点 &tex{Y_{1}};, &tex{Y_{2}}; の間には &tex{Y_{1}}; ∩ &tex{Y_{2}}; ≠ ∅ のとき辺がある

例えば X = {{1},{1,2,3},{3},{5,6},{6,7}} から作られるグラフは図のようになる。


#img(https://projecteuler.net/resources/images/0553-power-sets.gif, c)

このグラフは2つの''連結成分''を持つ。

C(n,k) を、R(n) の元のうちグラフがちょうど k 個の連結成分を持つようなものの個数と定める。&br;
C(2,1)=6, C(3,1)=111, C(4,2)=486, C(100,10) mod 1 000 000 007 = 728209718 である。

C(&tex{10^{4}};,10) mod 1 000 000 007 を求めよ。

IP:207.65.235.4 TIME:"2024-01-12 (金) 11:17:40" REFERER:"https://odz.sakura.ne.jp/projecteuler/?cmd=edit&page=Problem+553" USER_AGENT:"Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/120.0.0.0 Safari/537.36"