inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ 数学 Python プロジェクトオイラー http://projecteuler.net/ Q242. 集合{1,2,...,n}の部分集合を考える。要素数kの部分集合で総和が奇数のものの個数をf(n,k)とする。 n,k,f(n,k)がともに奇数のとき、odd-tripletと呼ぶ。n ≤ 1012でodd-tripletはいくつあるか。 ほぼ、数学だけで解ける。 以下、剰余は2で考える。 nとkは奇数以外興味がないから、 g(n,k) ≡ f(2n+1,2k+1) とする。 g(n,n) = (2n+1)(n+1) そうでないとき、例えば7までの集合から3個を選んで和が奇数のとき、6までから3個を選んで和が奇… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F20090723%2Fp1" title="Project Euler 242 - inamori’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-07-23 00:00:01 rich https://inamori.hateblo.jp/entry/20090723/p1 1.0 100%