SRM 508 Div1 Easy + Medium

Easy: 給了一個正整數$N$和最初放在第$M$格的物件，你可作如下操作﹕

(1) 把$N$除以其任意一個質因數$p$，並捨棄其他不包含該物件的區間。
(2) 把格子向左或右旋轉一下。

目標是要把物件放在第一格。問最少需要多少步才可。

首先一定要把$N$進行質因數分解。另外需要留意的是，兩個操順序後並無一定關係。可以考慮先處理(2)再處理(1)之前，把$N/p$個等分疊在一起，其結果就等價於先進行(1)再進行(2)。所以可以知道答案必定是先進行若干次(也可能完全沒有)劃分，然後考慮向左或向右旋轉至第一格最划算的費用之和。另，因為$M$是以$1$開始算的，所以要處理劃分後的位置必須先把$M$變成以$0$開始才可。假設劃分後$N'=N/p$，$M'=M \bmod{N'}$。剩下來就是怎樣選取劃分了。因為$N \le 1000000$，其互不相同的質因數最多只有$8$個，因此可以考慮枚舉$8!$的劃分順序。

Medium: 給了$N$個正整數$R_1\cdots R_n$，求有多少數數列$A_1\cdots A_n$使得

(1) $\sum_{i=1}^n A_i = A_1 | A_2 \cdots | A_n$。
(2) $A_i \le R_i$。

答案取模$10^9+9$。$1 \le R_i \le 10^{18}$，$1 \le N \le 10 $。

很難的題目。但$N$不大應該可以有一些牽涉$2^N$的動態規劃。未決定狀態之前，首先第條件(1)要求$A_i$必須不能在某一個二進位有多於一個$1$，而且二進位之間的關係是離散的，因此可以考慮二進位$p$為狀態之一。條件(2)限制了決定那個$A_i$的第$p$位應該取值$1$。因為如果某個$A_i$設為$1$的話可能使得$A_i > R_i$；但只要某些條件下不論$A_i$的第$p$位取值多少都不影響條件(2)。例如$R_i = 10101001_{(2)}, A_i = 101*...._{(2)}$，$*$只可以放$0$，否則會違反了條件(2)。但若$R_i = 10101001_{(2)}, A_i = 100*...._{(2)}$，$*$可以取任意值而不影響條件(2)。廣義一點來說，舉凡$A_i$在$p$位以左是$R_i$的前綴的話，則$A_i$在第$p$位的取值必須受$R_i$的$p$位影響，否則可取任意值。這首先說明了兩件事。第一是$p$必須從左至右有依賴性，第二是可以引入一種狀態，標示有多少個$A_i$是不再符合前綴條件。因為$N \le 10$，這個狀態可以用$2^N$來表示。因此便有$f(p, b)$，算出有多少個可行的方案，使得$p$位以左的二進位都符合條件，並且$b$表示了所有不符合$R_i$的集合。注意為方便，我把位元的算法是以$1$為開始的。已知對所有$b$，$f(0, b) = 1$，因為$p = 0$表示決定$A_i$取值的程序已經完成了。否則，其狀態轉移方程如下﹕
\[
f(p, b) = f(p-1, b') + \sum_{i=1}^N v_i \times f(p-1, b_i'')
\]

其中$b'$是代表在$p$位取$0$的情況下，有多少原本還是前綴的$A_i$現在已經不是了，並加入到$b$之中。
$b''_i$則是決定把$A_i$的$p$位取值為$1$，並根據計算$b'$的方法重新計算$b''_i$有些不再是前綴(留意有些必須前綴的數因為第$p$位的$1$被$A_i$佔用了，所以必須在其第$p$位放置$0$並不再是前綴)。有時候$A_i$是前綴並且$R_i$的$p$位是$0$，因此它不能取值$1$，所以不能把$f(p-1, b_i'')$算進去的，因此$v_i = 0$，其餘情況下都是$v_i = 1$。因此本題可以在$O(2^N\times N^2M)$時間內解決，其中$M$表示最長有多少位元。因為$R_i \le 10^{18}$，因此$M \le 60$。