トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

Problem201 唯一の和を持つ部分集合

問題

数の集合Aについて, sum(A)でAの要素の和を表す. 集合B = {1,3,6,8,10,11}を考えよう.
Bの3要素の部分集合は20個あり, それぞれ和は以下になる.

・sum({1,3,6}) = 10,
・sum({1,3,8}) = 12,
・sum({1,3,10}) = 14,
・sum({1,3,11}) = 15,
・sum({1,6,8}) = 15,
・sum({1,6,10}) = 17,
・sum({1,6,11}) = 18,
・sum({1,8,10}) = 19,
・sum({1,8,11}) = 20,
・sum({1,10,11}) = 22,
・sum({3,6,8}) = 17,
・sum({3,6,10}) = 19,
・sum({3,6,11}) = 20,
・sum({3,8,10}) = 21,
・sum({3,8,11}) = 22,
・sum({3,10,11}) = 24,
・sum({6,8,10}) = 24,
・sum({6,8,11}) = 25,
・sum({6,10,11}) = 27,
・sum({8,10,11}) = 29.

これらの和は1つしか現れない場合もそうでない場合もある.
集合Aについて, U(A,k)で, Aのk要素の集合全体について和を取ったときに1回のみ現れる和の集合を表す.
上の例をとると, U(B,3) = {10,12,14,18,21,25,27,29}であり, sum(U(B,3)) = 156 となる.

今, 100個の要素を持つ集合 S = {1の2乗, 2の2乗, ..., 100の2乗}を考える.
Sの50要素の部分集合は100891344545564193334812497256個ある.

50要素の部分集合の和の中で1回のみ現れる和の集合の総和を求めよ.
すなわち, sum(U(S,50))を求めよ.


ソース

作成中


実行結果

作成中


解説