作問ネタ・メモ (非常に雑多)

非常に雑多。しばらく作問もしないので、吐き出しておきます。

• 単純でない辞書順greedy
  • 辞書順最大の経路履歴みたいに極小・極大であることを利用するとか？

• 永続データ構造使いたい
  • meldable-Priority-queue
  • DPしたい

• 既存の計算結果を埋め込んでどうにかできるのとか面白そう
  • スパコンで計算されてるのは埋め込まざるをえない

• ケイリーの公式
  • n^k のnをmodで持つテクニックも使ってなんか

• Prüfer sequence
  • 木と一対一対応する長さ(n-2)の列
  • (木 <-> 列)、両方とも効率的に変換できる
    • priority_queueでO(n log n)でできそうだけど、Linearにはできるんだろうか？
  • iが出現する回数 = 頂点iの次数 - 1
    • 頂点iの次数がd_iである木の数 = 多項係数(n-2, [d_1-1, d_2-1, ..., d_n-1])
  • L,R頂点の完全二部グラフ上の木の数 = L^(R-1) - R^(L-1)

• Kirchhoff's theorem
  • 全域木の数 = Laplacian(G)の任意のcofactor(1行・1列を除去したもの)の行列式
  • Regular matroidに一般化できるそうだ

• 二項係数
  • wikipedia(en)に載っているものだけでも色々と公式が
    • WolframAlphaゲーになってしまうのはまあ…
    • Σ_(k = d..n) { C(n, k) - C(k, d) } = 2^(n-d) - C(n, d)
    • Σ_(k = 0..floor(n/2)) { C(n - k, k) } = Fibonacci(n - 1)
  • Lucas' theoremとその拡張
    • multinomialにも自然に拡張できる http://mathoverflow.net/questions/80169/reference-needed-for-lucas-theorem-for-multinomial-coefficients-modulo-a-prime

• いろんなデータ構造をデータ構造としてではなく扱う
  • AVL木
    • 2分木であって、左右の高さの差がたかだか1
    • f(h) = 高さhのAVL木が持つ頂点の最小数
    • f(0) = 0, f(1) = 1, f(h) = 1 - f(h-1) - f(h-2)
    • f(n) = fibonacci(n-2) - 1
    • 「頂点の最小数」を「辺の最小数」と言い換えれば、それ = fibonacci(n-2)

• 整数区間の包含関係のDAGはパスカルの三角形(の推移閉包)になっている
  • ある区間を拡大/縮小して別の区間にするやり方の数も二項係数
  • [l0, r0)を[l1, r1)に拡大するのは (x-y)! / x! y! = C(x-y, x) where x = (r1-r0); y = (l0-l1)

• Divisibility sequence http://en.wikipedia.org/wiki/Divisibility_sequence
  • フィボナッチ数はstrongに満たす
  • 第一種 Lucas sequence U_n(P, Q) はweakに満たす

• 確率だけど必ず0になる
  • 小数点k桁で四捨五入をさせるとか
  • 入力値の制約に下限を入れて

• bounded treewidthのtree decomposition上でのDP
  • 姉妹港で出ている。
  • グラフクラス上の効率的な解法の基本は、分解してDPだと思う
  • 様々な問題が様々なwidthに対してFPT。問題の宝庫。

• mod2のnCrをLucas'で桁ごとに分解し、1になるのがx>=y制約だと考えて最小カット的な