atcoder.jp 概要 N , Bで、次の条件を満たすようなものが何通りあるかを求めよ。ただし、非常に大きくなる場合があるので、で割ったあまりを求めること。 AとBの要素は、[1, M]の任意の整数 A[i] != B[i] (1 A[i] != A[j] (1 つまり、同じindexでのAとBの要…

つぎのような問題を考える。 サイズNの無向木が与えられる。木の頂点に色を塗っていき、隣あった頂点には同じ色を塗ってはならない。 木をちょうどK色で塗るとき、何通りの塗り分け方があるか？で割ったあまりを答えよ。制約： 2

atcoder.jp 概要 サイズNの木が与えられる。それぞれの辺に黒、白の二色のいずれかで塗る。 次のM個の条件をすべて満たす塗り方の場合の数を求めよ。 ・頂点u~頂点vを結ぶ経路の上に、必ず1つ以上の白く塗られた辺が存在する。制約: 1 min(20, (N-1)*N/2) AC…

atcoder.jp 概要 サイズNの木が与えられる。それぞれの頂点を1/2の確率で白、1/2の確率で黒と塗る。 黒で塗られた頂点をすべて含む最小部分木を考える。その最小部分木のサイズの期待値を求めよ。制約： 1

前編の読了お疲れさまでした。形式的べき級数でいくつかの数え上げを解決して、残るは数え上げの難関の3つの数(僕呼び)の、スターリング数、ベル数、分割数のみです。この三つの数はいずれも一般的な場合では漸化式を使わない式で表せません。今回の記事では…

先日、競プロやってたらhotmanから「形式的べき級数と数え上げの相性が抜群すぎてつながってて気持ちいい、世の中の眠る真理が目覚めた気がする」といわれて、気になったのでまとめた。 この記事は、数学的厳密性に欠けています。多くの変形が厳密な確認をな…