Problem 553
の編集
https://odz.sakura.ne.jp/projecteuler/?Problem+553
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
(no template pages)
*[[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 を求めよ。
タイムスタンプを変更しない
*[[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 を求めよ。
テキスト整形のルールを表示する
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
