…F(x) への復元も包除原理によって達成できる。F問題。自分は偶数個と奇数個で場合分けをした。この先では、選んだものを黒で塗り、選ばなかったものを白で塗ることにする。 偶数個のとき ２個ずつのまとまりにする。あるまとまりを見たとき、白と黒がひとつずつになっているはずである。さらに少し考えると次の形以外ありえないことがわかる。よって偶数個のときは累積和で解ける。 奇数個のとき 偶数個のときと同じように２個ずつのまとまりにする。ただし一つ余るはずである。あまったものは白であるとし…

…ようなものの数え方を包除原理と呼びます。天下り的に証明する方法もありますが、ここでは地道に導きました。条件が連言の場合のほかに、選言で表されている場合も似たような方法がとれます。よってこの問題は、「ある頂点からある頂点の間の辺がすべて白辺である」の形の複数の文の連言を条件とする問題を解けばよいです。これは易しい問題です。次は、ある頂点間を結ぶ道上の辺の列挙について考えます。深さ優先探索や幅優先探索などのアルゴリズムによって調べることができますが、次のようにもできます。まず適当…

…してしまう。そのため包除原理的に重複を除去していく。下側エラー→上側エラーとなるパターン数と上側エラー→下側エラーとなるパターン数もまた、先程と同様のテクニックにより計算できる（二回反転させる）。下側エラー→上側エラー→下側エラーというのも同様に計算できる（三階反転させる）。これらが計算できれば、包除原理的に解ける。下→上→下→上→…というのを永遠に求め続ける必要はなく、m の制約からして有限個である（m/n個程度であり、これは計算量に影響を与える）計算量はわかりづらいが、O…

…]-i|=Kを使って包除原理を行う。 たとえば K=2 だった場合、それぞれの事象は次のように表せる。 A[1]: a[1]=-1 または 3 A[2]: a[2]=0 または 4 <=== A[3]: a[3]=1 または 5 A[4]: a[4]=2 または 6 A[5]: a[5]=3 または 7 A[6]: a[6]=4 または 8 <=== ... A[2] の発生と A[6] の発生は依存関係があるが、A[2] と A[4] の発生には依存関係はない。一般に依存関…

…-|A \cap B|-|A \cap C| + |A \cap B \cap C| $$ 最後の式変形は包除原理を使った。包除原理が分からなくてもベン図で OK。 1..n の整数のうち k の倍数は $\lfloor n/k \rfloor$ 個である。このことを使えば f(i,j) も高速に計算できる。 i,j≦100 はあくまで計算量の見積もりの話で、実際は 109 をオーバーしたらループを終えるようにした方がオーバーフローしなくて安心。 med より簡単な気がする。

…。 これは、機械的に包除原理に放り込んでみたら気がついた。 ということで $$ a+b \le c $$ となる (a,b,c) の数を数える問題を考えてみよう。これは次の領域に含まれる格子点の数に等しい。 大きな三角錐から小さな三角錐を引いてあげれば格子点の数が求まる。A,Bが小さすぎて小さな三角形が重なってしまったら、重複分をキャンセルするように三角錐を足してあげればいい。 gist.github.com こういう数式系苦手なので、ひたすらそれっぽい式を立てて愚直解と比較…

…め方 全射の個数はスターリング数から計算できるので、スターリング数を計算しよう。 スターリング数の漸化式と3つの意味 | 高校数学の美しい物語 ちなみに包除原理でも求まる。 全射の個数の証明とベル数 | 高校数学の美しい物語 こっちだと 200 * 200 * 1000 * log2(1000) 程度のループが回るため多分 TLE する。（自分は TLE した。でも、冪乗を前計算すれば間に合う）。 yukicoder No.329 全射 問題イメージがなかなか捉えられず苦戦。