2012年8月26日星期日

Codeforces #132 (Div. 2) E - Periodical Numbers

Dynamic Scoring 是 3000 的題目 (所以也不是每個高手在現場解決了)
Virtual Participation 時花了 40 分鐘沒能搞定的題
不過當時有正確的大方向 (枚舉)

題意：

將一個正整數 X 表示為 n-bit 的 binary-string, S
不可以有前置零 (leading zeros)
若果存在 長度為 k < n 的 循環節 (period)
(i.e., 使得 S[i+k] = S[i]   for 0 <= i < n-k)
則稱 X 為 periodical

給定區間 [L, R], 問當中有多少個 periodical 的正整數

(題目連結)

思路：

先把問題簡化為
求 [1, R] 當中 periodical 正整數的個數
(那麼最後答案 := DOIT(R) - DOIT(L-1))

對於 循環節 長度為 k 的 X，可以將 X 表示成：
  • X = Y × (00...01 00...01 00...01 ... 00...01)   (二進制表示及計算，下同)
  • (00...01 00...01 00...01 ... 00...01) 是 m-bit 二進位數，其中 m <= n
  • 每一個 00...01 是 k-bit 二進位數

枚舉 m，再枚舉 k
可以容易求出 Y 的可能取值範圍 ---- (1)
 (若果把公式全部寫出來會 distract 本文中心思想，而且公式很容易推導，所以略去...)


可是，這樣會 double-count：
  • 比如，1111 在 k = 2, m = 4 及 k = 1, m = 4 被 double-count 了 ---- (2)

解決 double-count 問題：

固定 m，對於每一個 k | m
  • 設 g(k) := Y 的可能取值的個數
  • 設 f(k) := 最短 period 是 k 而且 <= R 的 periodical number
    (e.g., 10101010 的最短 period 是 2 而不是 4)

易知 (as an example)：
  • g(4) := f(1) + f(2) + f(4)

更一般地：
  • g(k) := f(d1) + f(d2) + ... f(dr)
    其中 di's 是 k 的因數

g(k) 的值很容易 求出 (見 (1))，但有 double-count (見 (2))
而 f(k) 則是我們最終想得出的值，而每一個 periodical number 僅被包含在一個 f(k) 裏

若果有一個方法，可以由 g 恢復出 f
那麼這一題就 Q.E.D.了...

其實這樣的一個方法是存在的！

Mobius Inversion Formula：

(Wikipedia)

若果有
g(n)=\sum_{d\,\mid \,n}f(d)\quad\text{for every integer }n\ge 1
則
f(n)=\sum_{d\,\mid\, n}\mu(d)g(n/d)\quad\text{for every integer }n\ge 1
其中 μ 是 Möbius function 及 d's 是 n 的所有因數
(其實在以前的 blog 已經提及過，當時說過想寫一篇 blog 較深入地談一下 ，但一直沒有時間沒遇到好題目太懶)

計算 Mobius function 的算法：

可以證明 μ 是 唯一的 (證明略)

特別地，我們可以代入
  • f(n) := 1  if n = 1
  • f(n) := 0  if n > 1
使得
  • g(n) := 1 for all n
從而反過來求出 μ(n) 的值

以下是一段 psuedocode --- (3)：

　μ(1) := 1
　For i := 1 to N
　　For j := 2i, 3i, ... ki and ki <= N
　　　μ(j) := μ(j) - μ(i)
　　EndFor
　EndFor

總結 - 題解(算法)：

DOIT(R) := 計算 <= R 的 periodical number 的個數：
  1. 先計算 Mobius Function - μ(N) (見 (3))
  2. 枚舉 periodical 二進位數的長度 m
  3. 枚舉 循環節 (period) 長度 k ，其中 k | m，計算 g(k) (見 (1))
  4. 利用 1. 及 3., 計算 f(k)
  5. 把所有 f(k) 加起來：
    Answer := sum of f(k), 其中每個 k != m 是 m 的 因數
最後答案 :=  DOIT(R) - DOIT(L-1)


結語：

其實這條題目的 tag 是 DP
其中思想就是小心處理 double-count 吧
只是，題目真的可以用 Mobius Inversion Formula 這件高級武器解決
所以才決心試寫一下(both code + blog)

我第一次遇見 Mobius Function 是在 Facebook HackerCup 2011 Round 2 (Blog 連結)
當時有一道 combinatorics / counting 的題目
發現 double-count 的問題挺難處理
(但奈何其它題目太難，感覺這是唯一一道有機會解決的題目)
畫了好幾個 example + 想了很久之後
發現 double-count 可以透過考慮 square-free number 及 # prime factor
來決定是 + 或 -
當時寫了一個 dfs 做這項工作，dfs 應該對的，可惜是我把 g(.) (較簡單的一步) 寫錯了... orz

原來不知不覺地當時推出了 Mobius Function：
  • μ(n) := 0             if n is not square-free
  • μ(n) := (-1)^m    if n is square-free, and m := # prime factors of n

其後，自己閱讀了一些有關 Mobius Function 的 note
發現 Mobius Function 可以由 正整數集合 推廣到 Partially-Ordered Set (Poset)
而且，Inclusion-Exclusoin Principle 正是 Mobius Function 的一個特例
由於篇幅所限(而且自己還未完全看懂)，有興趣的讀者可以參閱(感覺上寫得挺好的)：

Reference：
  1. Möbius inversion formula - Wikipedia
  2. Möbius function - Wikipedia
  3. Möbius inversion and Inclusion/Exclusion
發佈者： 於
標籤： , ,

沒有留言:

發佈留言

訂閱： 發佈留言 (Atom)